/* 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
搜索
最新评论
|
|