学步园

思路：总共有2^10的状态，枚举每一个状态用01背包判断是否此状态可以一次运走，并记录下来，接下来又用每一个可以一趟就运走的状态看成一个01背包问题中要装的物品，求出最小的运送的次数。

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define CL(a,b) memset(a,b,sizeof(a))
#define MIN(a,b) a<b?a:b
#define MAX(a,b) a>b?a:b
using namespace std;
const int M(107);
int c1,c2,a[M],f[M],n;
int state[1200],dp[1200];
inline bool judge(int s)
{
	int i,sum=0,j;
	CL(f,0);
	for(i=0;i<n;i++)
		if(s&(1<<i))
		{
			sum+=a[i];
			for(j=c1;j>=a[i];j--)
				f[j]=MAX(f[j-a[i]]+a[i],f[j]);
		}
	if(sum-f[c1]<=c2)return true;
	return false;
}
int main()
{
	int t,i,j,k,l;
	scanf("%d",&t);
	for(l=1;l<=t;l++)
	{
		scanf("%d%d%d",&n,&c1,&c2);
		if(c1<c2)swap(c1,c2);
		for(i=0;i<n;i++)
			scanf("%d",&a[i]);
		for(i=0,k=0;i<(1<<n);i++)
		{
			if(judge(i))state[k++]=i;//记录两辆车一趟可以运走的状态。
			dp[i]=100000000;
		}
		dp[0]=0;
		for(i=0;i<k;i++)
			for(j=(1<<n)-1;j>=0;j--)
					if(!(j&state[i]))//去除重复覆盖（重复运送同一个物品）
						dp[j|state[i]]=MIN(dp[j|state[i]],dp[j]+1);

		printf("Scenario #%d:\n",l);
		printf("%d\n",dp[(1<<n)-1]);
		if(l!=t)
			printf("\n");
	}
}