首页 > 代码库 > hdu 1059 Dividing 多重背包
hdu 1059 Dividing 多重背包
就是看能不能装满给定容量的背包。
#include <stdio.h>#include <string.h>int dp[200000],a[15];int main(){ int cas=0,c; int i,j,k; while(1) { int sum=0; cas++; for(i=1;i<=6;i++) { scanf("%d",&a[i]); sum+=a[i]*i; } if(sum==0) break; printf("Collection #%d:\n",cas); if(sum%2!=0) { printf("Can‘t be divided.\n\n"); continue; } sum/=2; memset(dp,0,sizeof(dp)); dp[0]=1; for(i=1;i<=6;i++) { if(a[i]==0) continue; for(j=1;j<=a[i];j*=2) { c=j*i; for(k=sum;k>=c;k--) if(dp[k-c]) dp[k]=1; a[i]-=j; } c=a[i]*i; if(c!=0) { for(k=sum;k>=c;k--) if(dp[k-c]) dp[k]=1; } } if(dp[sum]) printf("Can be divided.\n\n"); else printf("Can‘t be divided.\n\n"); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。