poj 1014 Dividing（多重背包可行性解）

多重背包可行性模板题（能否把背包装满）

用了背包九讲中的模板，dp[i][j]表示用前i个物品装满j空间的背包最多剩下多少个第i种物品。

初始化除了dp[0][0]是合法的，赋0，其余全部赋-1（不合法）

注意说最大20000指的是雕像的数量，所以数组应该开到120000，因为这个re了一次

代码：

#include 
#include 
#include 
using namespace std;int dp[7][120005];
int a[7];
int main(){int flag=1;while(~scanf("%d%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6])){int sum=0;for(int i=1;i<=6;i++){sum+=a[i]*i;}if(sum==0) break;printf("Collection #%d:\n",flag++);if(sum%2){printf("Can't be divided.\n\n");continue;}memset(dp,-1,sizeof(dp));dp[0][0]=0;sum/=2;for(int i=1;i<=6;i++){for(int j=0;j<=sum;j++){if(dp[i-1][j]>=0){dp[i][j]=a[i];}else dp[i][j]=-1;}for(int j=0;j<=sum-i;j++){if(dp[i][j]>0){dp[i][j+i]=max(dp[i][j+i],dp[i][j]-1);}}}if(dp[6][sum]>=0) printf("Can be divided.\n\n");else printf("Can't be divided.\n\n");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！