【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[ << N],cnt;

void solve()

{

    int dp[N * M], sum;

    for(int i = ; i < U; i++)

    {

        memset(dp, , sizeof dp);

        dp[] = ;

        sum = ;

        for (int j = ; j < n; j++)

        {

            int x =  << j;

            if (x & i)//i状态里有第j个货物

            {

                sum += w[j];//一边累加该状态的总重量

                for (int k = c1 - w[j]; k >= ; k--)

                {

                    if (dp[k])//c1装k重量行不行

                        dp[k + w[j]] = ;

                }

            }

        }

        for(int k = ; k <= sum; k++)

            if (dp[k] && sum - k <= c2)

            {

                s[i] = ;//i状态需要一次车程运送过去。

                break;

            }

    }

}

int dp()

{

    for (int i = ; i < U; i++)

        if (s[i])

            for (int j = ; j < U - i; j++)

                if ((j & i) ==  && s[j]) //i状态和j状态都是可以运送过去的，且i和j没有重合的货物

                    if (s[i | j] ==  || s[i | j] > s[i] + s[j])//i+j状态原来不能运送过去，或者原来运送过去的次数更大

                        s[i | j] = s[i] + s[j];//更新

    return s[U - ];

}

int main()

{

    scanf("%d", &t);

    for(int sc = ; sc <= t; sc++)

    {

        memset(s, , sizeof s);

        scanf("%d%d%d", &n, &c1, &c2);

        for(int i = ; i < n; i++) scanf("%d", &w[i]);

        solve();

        printf("Scenario #%d:\n%d\n\n", sc, dp());

    }

    return ;

}