POJ2923dp状态压缩

原文链接: POJ 2923 dp 状态压缩

上一篇: HDU 1010 dfs 奇偶剪枝

下一篇: POJ 2362/HDU 1518 dfs 剪枝

dp

/*POJ 2923解法为状态压缩DP+背包，本题的解题思路是先枚举选择若干个时的状态，总状态量为1<
#include
#include
#include
#include
using namespace std;
const int INF = 0x3f3f3f3f;
int state[1030];
int tol;
int dp[1030];
int n, C1, C2;
int cost[110];
int vis[1030];
int dp2[1030];//判断状态是否满足要求,先按照01背包,然后看剩下的第二个是不是可以装走
bool judge2(int x){memset(dp2, 0, sizeof(dp2));memset(vis, 0, sizeof(vis));int cnt = 1, sum = 0;for (int i = 0; i C1 + C2)return 0;for (int i = 1; i <= cnt; i++)dp2[i] = 0;for (int i = 1; i <= cnt; i++){for (int v = C1; v >= vis[i]; v--)dp2[v] = max(dp2[v], dp2[v - vis[i]] + vis[i]);}if (dp2[C1] + C2 }//判断x是否满足状态
bool judge(int x){int sum = 0;memset(vis, 0, sizeof(vis));//第一辆车可以不装vis[0] = true;//遍历每一个位置for (int i = 0; i = cost[i]; j--)if (vis[j - cost[i]]) //如果放入后的状态可行,则该状态可行vis[j] = true;}}//如果总数太多if (sum > C1 + C2)return false;//遍历第一辆车可以装的数目,如果第一辆车可以装这么多,并且剩下的第二辆车也能装下 for (int i = 0; i <= C1; i++)if (vis[i] && sum - i <= C2)return true;return false;
}
int main(){freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);int T;int iCase = 0;scanf("%d", &T);while (T--){iCase++;scanf("%d%d%d", &n, &C1, &C2);for (int i = 0; i = 0; j--){if (dp[j] == INF) continue;if ((j & state[i]) == 0){dp[j | state[i]] = min(dp[j | state[i]], dp[j] + 1);}}printf("Scenario #%d:\n%d\n\n", iCase, dp[(1 <}


记忆化搜索

#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define myabs(x) ((x) > 0 ? (x) : (-(x)))
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = (1 <<10) + 10;
int f[maxn], goods[maxn];
int damn[110];
int w[15];
int n, c1, c2, tot;
int judge(int x){int i, j;memset(damn, 0, sizeof(damn));int sum = 0;for (i = 0; (1 <= w[i + 1]; j--)damn[j] = max(damn[j], damn[j - w[i + 1]] + w[i + 1]);}}if (sum - damn[c1] <= c2) return 1;else return 0;
}
int dfs(int sta){if (f[sta] != -1) return f[sta];if (sta == 0) return 0;int i;f[sta] = inf;int tem;for (i = 0; i = goods[i] && ((sta - goods[i]) & goods[i]) == 0){tem = dfs(sta - goods[i]) + 1;if (tem }
int main(){int T;cin >> T;int cas = 0;while (T--){scanf("%d%d%d", &n, &c1, &c2);int i;tot = 0;for (i = 1; i <= n; i++)scanf("%d", &w[i]);for (i = 1; i <(1 <}