多重背包--zoj_2156
???????? 首先介绍经典的三种背包问题，0-1背包，完全背包，多重背包。0-1背包是背包问题的最简形式，其他的很多背包问题都可以转化为0-1背包来解决，而0-1背包问题也有非常简单的解法，时间效率为O(V*N),空间消耗为O(V),这里不要小看空间消耗，在数据量很大时，大量的取地址操作也会占用不少的时间消耗。
??????? 0-1背包问题可以这样描述：给出N个背包，每个背包的重量为c[i]，价值为v[i]，在N个背包中选取k个，每个最多选1次，使得总的重量小于V而，总的价值最大。
??????? 用DP，以dp[i][j]表述更新第i个背包，总重量为j时的最大价值。显然可以有以下状态转移方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+v[i]);简单分析一下效率发现是O(V*N),空间消耗为O(V*N).
?????? 那么如何简化空间消耗呢，运用了很巧妙的一个技巧,在遍历j时从大到小遍历即可用dp[j]表示新第i个背包，总重量为j时的最大价值。仔细想想WSM会这样呢？如果从小到大遍历
dp[j]是由dp[j]和dp[j-c[i]]+v[i]更新而来的，而此时的dp[j]已经是dp[i][j]了，但我们需要的是dp[i-1][j]。仔细想想就可以明白。
??????? 完全背包问题可以这样描述：给出N个背包，每个背包的重量为c[i]，价值为v[i]，在N个背包中选取k个，每个次数不限，使得总的重量小于V而，总的价值最大。
?????? 朴素的解法就是在0-1背包的基础上遍历k，分析一下效率为V*sum(V/c[i])
?????? 也有拆分法效率为V*sum(log(V/c[i]))，具体见背包9讲
?????? 这里要重点介绍O(V*N)法，很简单也很巧妙，就是0-1背包优化解法的正向更新，在遍历j时从小到大遍历即可用dp[j]表示新第i个背包，总重量为j时的最大价值。
?????? WSM会这样呢？仔细想想也很简单，在0-1背包的时候，我们希望更新dp[j]的时候dp[j]和dp[j-c[i]]+v[i]都是在i-1时更新的值，而在完全背包时，每个背包可以取无限次，因此我们在更新dp[j]的时候恰恰需要的是在i时的dp[j]和dp[j-c[i]]+v[i]。
?????? 最后介绍多重背包：给出N个背包，每个背包的重量为c[i]，价值为v[i]，在N个背包中选取k个，每个次数为n[i]，使得总的重量小于V而，总的价值最大。
?????? 显然也可以遍历k，效率是V*sum(n[i]),这里介绍一种拆分法V*sum(log(n[i])),
很简单，把每一个系数为n[i]的背包拆分为，系数为2^0,2^1,2^2...n[i]-2^k的背包，背包的重量和价值都乘上相对应的系数即可。拆分后用0-1背包解。
zoj_2156
#include<cstdio>#include<algorithm>using namespace std;pair<int,int> clist[200];int p,c1,c2,c3,c4;int total,mid;int inf=-999999;//int dp[200][10005];int dp[10005];//int path[200][10005];int path[10005];int cnt[10005];int flag[200];void init(){total=0;int tmp=1;mid=c1;while(mid>tmp){mid=mid-tmp;clist[++total]=make_pair(1*tmp,1*tmp);flag[total]=1;tmp*=2;}clist[++total]=make_pair(1*mid,1*mid);flag[total]=1;mid=c2;tmp=1;while(mid>tmp){mid=mid-tmp;clist[++total]=make_pair(5*tmp,1*tmp);flag[total]=2;tmp*=2;}clist[++total]=make_pair(5*mid,1*mid);flag[total]=2;mid=c3;tmp=1;while(mid>tmp){mid=mid-tmp;clist[++total]=make_pair(10*tmp,1*tmp);flag[total]=3;tmp*=2;}clist[++total]=make_pair(10*mid,1*mid);flag[total]=3;mid=c4;tmp=1;while(mid>tmp){mid=mid-tmp;clist[++total]=make_pair(25*tmp,1*tmp);flag[total]=4;tmp*=2;}clist[++total]=make_pair(25*mid,1*mid);flag[total]=4;return;}void solve(){/*for(int i=0;i<=total;++i)for(int j=0;j<=p;++j){dp[i][j]=inf;}*/for(int j=0;j<=p;++j){dp[j]=-1;cnt[j]=0;}dp[0]=0;/*for(int i=1;i<=total;++i){for(int j=0;j<=p;++j){if(j-clist[i].first>=0){if(dp[i][j]<dp[i-1][j-clist[i].first]+clist[i].second&&dp[i-1][j-clist[i].first]+clist[i].second>=0){path[i][j]=flag[i];dp[i][j]=dp[i-1][j-clist[i].first]+clist[i].second;}else{path[i][j]=0;}//dp[i][j]=max(dp[i][j],dp[i-1][j-clist[i].first]+clist[i].second);}if(dp[i][j]<dp[i-1][j]&&dp[i-1][j]>=0){dp[i][j]=dp[i-1][j];path[i][j]=0;}//dp[i][j]=max(dp[i][j],dp[i-1][j]);}}*/for(int i=1;i<=total;++i){for(int j=p;j>=clist[i].first;--j){if(dp[j]<dp[j-clist[i].first]+clist[i].second&&dp[j-clist[i].first]!=-1){path[j]=j-clist[i].first;cnt[j]=flag[i];dp[j]=dp[j-clist[i].first]+clist[i].second;}}}}int main(){freopen("e:\\zoj\\zoj_2156.txt","r",stdin);while(scanf("%d %d %d %d %d",&p,&c1,&c2,&c3,&c4)!=EOF){if(p==0&&c1==0&&c2==0&&c3==0&&c4==0)break;init();solve();if(dp[p]<0)puts("Charlie cannot buy coffee.");/*if(dp[total][p]<0)puts("Charlie cannot buy coffee.");*/else{//printf("%d\n",dp[total][p]);int c,n,d,q;c=n=d=q=0;int tmp=p;/*for(int i=total;i>=1;--i){if(path[i][tmp]==0)continue;else{if(path[i][tmp]==1){tmp-=clist[i].first;c+=clist[i].first/1;}if(path[i][tmp]==2){tmp-=clist[i].first;n+=clist[i].first/5;}if(path[i][tmp]==3){tmp-=clist[i].first;d+=clist[i].first/10;}if(path[i][tmp]==4){tmp-=clist[i].first;q+=clist[i].first/25;}}}*/while(tmp>0){if(cnt[tmp]==0)continue;else{if(cnt[tmp]==1){c+=(tmp-path[tmp])/1;tmp=path[tmp];}if(cnt[tmp]==2){n+=(tmp-path[tmp])/5;tmp=path[tmp];}if(cnt[tmp]==3){d+=(tmp-path[tmp])/10;tmp=path[tmp];}if(cnt[tmp]==4){q+=(tmp-path[tmp])/25;tmp=path[tmp];}}}printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",c,n,d,q);}}}?
背包模板,zoj_2156
#include <iostream>#include <cstring>#include <cstdio>using namespace std;#define maxn 10002int num[4],v[4],ans[4];int sum;int dp[maxn];int fa[maxn];int cnt[maxn];void pack1(int c,int k) //0 1 背包{ int v; for (v = sum;v>=c;v--) { if (dp[v] < dp[v-c]+k && dp[v-c]!=-1) { fa[v] = v - c; cnt[v] = k; dp[v] = dp[v-c]+k; } } return;}void pack2(int c) //完全背包{ int v; for (v = c;v<=sum;v++) { if (dp[v] < dp[v-c] + 1 && dp[v-c]!=-1) { fa[v] = v-c; cnt[v] = 1; dp[v] = dp[v-c] + 1; } } return;}void pack3(int c,int a) //多重背包{ if (c*a>=sum) { pack2(c); return; } int k = 1; while (a-k>0) { pack1(k*c,k); a = a - k; k*=2; } pack1(a*c,a); return;}int main(){ int i,tmp,k1; v[0] = 1; v[1] = 5; v[2] = 10; v[3] = 25;freopen("e:\\zoj\\zoj_2156.txt","r",stdin); while (scanf("%d%d%d%d%d",&sum,&num[0],&num[1],&num[2],&num[3])) { if (sum==0&&num[0]==0&&num[1]==0&&num[2]==0&&num[3]==0) break; memset(dp,-1,sizeof(dp)); dp[0] = 0; for (i=0;i<4;i++) pack3(v[i],num[i]); if (dp[sum] != -1) { tmp = sum; memset(ans,0,sizeof(ans)); while (tmp!=0) { k1 = (tmp - fa[tmp])/cnt[tmp]; if (k1 == 25) ans[3] += cnt[tmp]; else if (k1 == 10) ans[2] += cnt[tmp]; else if (k1 == 5) ans[1] += cnt[tmp]; else ans[0] += cnt[tmp]; tmp = fa[tmp]; } printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",ans[0],ans[1],ans[2],ans[3]); } else printf("Charlie cannot buy coffee.\n"); } return 0;}?
?