【POJ 2923】Relocation（状压DP+DP）

题意是给你n个物品，每次两辆车运，容量分别是c1，c2，求最少运送次数。
好像不是很好想，我看了网上的题解才做出来。
先用状压DP计算i状态下，第一辆可以运送的重量，用该状态的重量总和-第一辆可以运送的，如果小于c2，那么可以一次运送i状态里的货物。
然后再用DP把s【i】为i状态的运送次数，通过转移方程s[i | j] = min{s[i | j] ,s[i] + s[j]}计算出全部运送过去的最少次数。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 11
#define M 102
#define U (1<<n)
using namespace std;
int t, n, c1, c2, w[N];
int s[1 << N],cnt; 
 
void solve()
{
    int dp[N * M], sum;
    for(int i = 1; i < U; i++) 
    {
        memset(dp, 0, sizeof dp); 
        dp[0] = 1;
        sum = 0;
        for (int j = 0; j < n; j++)
        {
            int x = 1 << j;
            if (x & i)//i状态里有第j个货物
            {
                sum += w[j];//一边累加该状态的总重量
                for (int k = c1 - w[j]; k >= 0; k--)
                {
                    if (dp[k])//c1装k重量行不行
                        dp[k + w[j]] = 1;
                }
            }
        }
 
        for(int k = 0; k <= sum; k++)
            if (dp[k] && sum - k <= c2)
            {
                s[i] = 1;//i状态需要一次车程运送过去。
                break;
            }
    }
}
 
int dp()
{
    for (int i = 0; i < U; i++)
        if (s[i])
            for (int j = 0; j < U - i; j++)
                if ((j & i) == 0 && s[j]) //i状态和j状态都是可以运送过去的，且i和j没有重合的货物
                    if (s[i | j] == 0 || s[i | j] > s[i] + s[j])//i+j状态原来不能运送过去，或者原来运送过去的次数更大
                        s[i | j] = s[i] + s[j];//更新
    return s[U - 1];
}
 
int main()
{
    scanf("%d", &t);
    for(int sc = 1; sc <= t; sc++)
    {
        memset(s, 0, sizeof s);
        scanf("%d%d%d", &n, &c1, &c2);
        for(int i = 0; i < n; i++) scanf("%d", &w[i]);
        solve();
        printf("Scenario #%d:
%d

", sc, dp());
    }
    return 0;
}