poj 1014 多重背包

很明显，这题是多重背包，参见背包九讲就可以做出来了，然后有个小问题就是 背包九讲上面的 伪代码 有点小问题，就是 进行二进制拆分的时候，while(k<num)应该是

while(k<amount),不知道是不是我看的版本太旧了，背包不怎么会，在那边RE了无数次。。

#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;const int maxn=20005;int cnt[7],V;int dp[maxn*3];void ZeroOnePack(int cost,int weight){//0-1背包for(int i=V;i>=cost;i--){dp[i]=max(dp[i],dp[i-cost]+weight);}}void CompletePack(int cost,int weight){//完全背包for(int i=cost;i<=V;i++){//与01背包顺序相反dp[i]=max(dp[i],dp[i-cost]+weight);}}void MultiplePack(int cost,int weight,int amount){//多重背包if(cost*amount>=V){CompletePack(cost,weight);return;}else {int k=1;while(k<amount){//二进制拆分ZeroOnePack(k*cost,k*weight);amount-=k;k*=2;}ZeroOnePack(amount*cost,amount*weight);}}int main(){int cas=0;while(scanf("%d",&cnt[1])==1){V=cnt[1];for(int i=2;i<=6;i++)scanf("%d",&cnt[i]),V+=cnt[i]*i;if(V==0)break;printf("Collection #%d:\n",++cas);if(V%2)puts("Can't be divided.");else {V/=2;memset(dp,0,sizeof(dp));for(int j=1;j<=6;j++){if(cnt[j])MultiplePack(j,j,cnt[j]);}if(dp[V]==V)puts("Can be divided.");else puts("Can't be divided.");}puts("");}}