/* http://hi.baidu.com/forverlin1204/blog/item/96eeab102a2a6dcda6ef3f61.html 狀態壓縮DP 給定兩輛車的容量c1,c2,物品的個數n,每件物品的重量w[i],要使來回趟數盡可能少 枚舉1<<n種組合,看哪些物品可以由兩輛車一次運走,然后DP求至少要運的次數 state存儲可以一次由兩輛車運完的狀態 */ #include<cstdio> #include<cstring>
int n,c1,c2; int w[12],v[12]; int dp[1<<11]; int state[1<<11],tot;
//選中k個,再用2進制組合 void comb(){ int limit=1<<n; tot=0; for(int i=1;i<limit;i++){ int k=0; for(int t=0;t<n;t++)if(i&(1<<t))v[k++]=w[t]; int klimit=1<<k; for(int j=0;j<klimit;j++){//組合 check, 1誰取,0誰取,注意j=0開始 int t1=c1,t2=c2; for(int t=0;t<k;t++){ if(j&(1<<t))t1-=v[t]; else t2-=v[t]; if(t1<0||t2<0)break; } if(t1>=0&&t2>=0){state[++tot]=i;break;} } } } void DP(){//0-1 memset(dp,-1,sizeof(dp)); dp[0]=0; for(int i=1;i<=tot;i++) for(int j=(1<<n)-1-state[i];j>=0;j--){ if(dp[j]<0)continue; int k=j+state[i]; if((j|state[i])!=k)continue;// if(dp[k]==-1||dp[k]>dp[j]+1)dp[k]=dp[j]+1; } } int main(){ int T,t=1; scanf("%d",&T); while(T--){ scanf("%d%d%d",&n,&c1,&c2); for(int i=0;i<n;i++) scanf("%d",&w[i]); comb(); DP(); printf("Scenario #%d:\n%d\n\n",t++,dp[(1<<n)-1]); } return 0; }
|
|
常用鏈接
隨筆分類
Links
搜索
最新評論

|
|