POJ 2923 Relocation（状压DP）题解

题意：有2辆车运货，每次同时出发，n（<10），各自装货容量c1 c2，问最少运几次运完。

思路：n比较小，打表打出所有能运的组合方式，用背包求出是否能一次运走。然后状压DP运的顺序。

代码：

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1024 + 10;
const int M = maxn * 30;
const ull seed = 131;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int c1, c2, n;
int w[maxn];
int dp[1 << 12];
int can[maxn];
int bag[maxn], v[maxn];
int main(){
    int T, ca = 1;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d", &n, &c1, &c2);
        for(int i = 0; i < n; i++) scanf("%d", &w[i]);

        int cnt = 0;
        int tot = 0, sum = 0;
        for(int i = 1; i < (1 << n); i++){
            tot = sum = 0;
            for(int j = 0; j < n; j++){
                if(i & (1 << j)) v[++tot] = w[j], sum += w[j];
            }
            memset(bag, 0, sizeof(bag));
            for(int j = 1; j <= tot; j++){
                for(int k = c1; k >= v[j]; k--){
                    bag[k] = max(bag[k], bag[k - v[j]] + v[j]);
                }
            }
            if(c2 >= sum - bag[c1]) can[cnt++] = i;
        }

        memset(dp, INF, sizeof(dp));
        dp[0] = 0;
        for(int i = 0; i < (1 << n); i++){
            if(dp[i] == INF) continue;
            for(int j = 0; j < cnt; j++){
                if((i & can[j]) == 0){
                    dp[i | can[j]] = min(dp[i | can[j]], dp[i] + 1);

                }
            }
        }

        printf("Scenario #%d:
%d

", ca++, dp[(1 << n) - 1]);
    }
    return 0;
}