题意是给你n个物品，每次两辆车运，容量分别是c1，c2，求最少运送次数。 好像不是很好想，我看了网上的题解才做出来。 先用状压DP计算i状态下，第一辆可以运送的重量，用该状态的重量总和-第一辆可以运送的，如果小于c2，那么可以一次运送i状态里的货物。 然后再用DP把s【i】为i状态的运送次数，通过转移方程s[i | j] = min{s[i | j] ,s[i] s[j]}计算出全部运送过去的最少次数。
代码语言：javascript复制#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:n%dnn", sc, dp());
}
return 0;
}
