http://www.cnblogs.com/kuangbin/archive/2012/09/14/2685430.html
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define MAXN 1010 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f int n,c1,c2; bool vis[1030]; int w[105],dp[1030]; int state[1030]; bool judge(int x) { mem(vis,false); vis[0] = true; int i,j,sum=0; for(i=0;i<n;i++) { if((1<<i)&x) { sum+=w[i]; for(j=c1;j>=w[i];j--) { //记录c1中所有可能的重量值 if(vis[j-w[i]]) vis[j]=true; } } } if(sum>c1+c2) return false; for(i=0;i<=c1;i++) { //判断c2中能不能接受这个值 if(vis[i] && sum-i<=c2) return true; } return false; } int main() { int t,i,j; sf("%d",&t); int iCase=0; while(t--) { mem(w,0); iCase++; sf("%d%d%d",&n,&c1,&c2); for(i = 0;i<n;i++) { sf("%d",&w[i]); } int tot = 0; for(i=0;i<(1<<n);i++) dp[i]=INF; dp[0] = 0; for(i=0;i<(1<<n);i++) { if(judge(i)) { state[tot++] = i; } } for(i=0;i<tot;i++) { for(j=(1<<n)-1;j>=0;j--) { if(dp[j]==INF) continue; if((j&state[i]) == 0) { dp[j|state[i]] = min(dp[j]+1,dp[j|state[i]]); } } } pf("Scenario #%d: %d ",iCase,dp[(1<<n)-1]); } return 0; }