比較綜合的題目。
有n個物品，有兩輛車載重分別是c1,c2.問需要多少趟能把物品運完。
n比較小，只有10，而且需要把所有物品全部運完，便想到狀態壓縮來保存狀態。
首先記錄好所有的可行狀態，對於狀態state能一趟運完。
然後再利用01背包，dp[j]，表示已運的狀態為j，如果狀態j與ok[i]不沖突，則可以從狀態j運一趟變為j|ok[i]。
dp[j|ok[i]]=min(dp[j|ok[i]],dp[j]+1);
[cpp]
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<queue>
#include<string>
#include<vector>
#define eps 1e-6
#define LL long long
#define LD long double
#define pi acos(-1.0)
#define inf 1<<30
using namespace std;
int n,c1,c2,cnt,w[10];
int ok[1<<10]; //能一次裝過去的可行狀態
int dp[1<<10];
bool judge(int state){ //判斷state狀態的物品能否一次運走
int sum=0;
int f[105];
memset(f,0,sizeof(f));
f[0]=1;
for(int i=0;i<n;i++)
if((1<<i)&state){
sum+=w[i];
for(int j=c1;j>=w[i];j--) //01背包判斷可行否
f[j]=max(f[j-w[i]],f[j]);
}
if(sum>c1+c2) //如果總重量超過了兩個車之和
return false;
for(int i=0;i<=c1;i++) //如果i可放c1,另外 一部分可以放入c2,則可行
if(f[i]&&sum-i<=c2)
return true;
return false;
}
int main(){
int t,cas=0;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&c1,&c2);
for(int i=0;i<n;i++)
scanf("%d",&w[i]);
cnt=0;
for(int i=0;i<(1<<n);i++){
dp[i]=inf;
if(judge(i))
ok[cnt++]=i;
}
dp[0]=0;
for(int i=0;i<cnt;i++)
for(int j=0;j<(1<<n);j++)
if(!(ok[i]&j)) //如果兩個狀態沒有沖突
dp[j|ok[i]]=min(dp[j|ok[i]],dp[j]+1); //在j的基礎上再加入狀態ok[i]
printf("Scenario #%d:\n%d\n\n",++cas,dp[(1<<n)-1]);
}
return 0;
}
作者：ACM_cxlove
