《背包九讲》由会员分享，可在线阅读，更多相关《背包九讲（12页珍藏版）》请在金锄头文库上搜索。
1、背包,Copy right中国地质大学（北京）ACM/ICPC 集训队,九,讲,By wgx998877,背包问题及其变化,01背包 ZeroOnePack,完全背包 CompletePack,多重背包 MultiplePack,混合背包 MixedPack,泛化物品,有依赖背包,二维费用背包,分组背包,01背包 ZeroOnePack,有N件物品和一个容量为V的背包。第i件物品的费用是ci，价值是wi。求解将哪些物品装入背包可使价值总和最大。,这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即fiv表示前i件物品恰放入一个容量为v的背包可以获得的最大价值
2、。则其状态转移方程便是：,fiv=maxfi-1v,fi-1v-ci+wi,void OneZeroPack(int cost,int value) int i,j; for(i = total;i = cost; i-) fi = max(fi,fi-cost+value); ,逆序！ 这就是关键！ 1 for i=1N 2 for v=V0 3 fv=max fv,fv-ci+wi; 4 分析上面的代码：当内循环是逆序时 就可以保证后一个fv和fv-ci+wi是前一状态的！ 这里给大家一组测试数据： 测试数据： 10,3 3,4 4,5 5,6,Cv从物品i=1开始，循环到物品3，期间，每
3、次逆序得到容量v在前i件物品时可以得到的最大值。,hdu2602,Sample Input 1 5 10 1 2 3 4 5 5 4 3 2 1 Sample Output 14,hdu2602,有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是ci，价值是wi。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。,完全背包 CompletePack,void completePack(int cost,int weight) int i; for(i = cost;i = total; i+) fi = max(fi,fi-cost+weigh
4、t); ,CompletePack,顺序！ 想必大家看出了和01背包的区别，这里的内循环是顺序的，而01背包是逆序的。 现在关键的是考虑：为何完全背包可以这么写？ 在次我们先来回忆下，01背包逆序的原因？是为了是max中的两项是前一状态值，这就对了。 那么这里，我们顺序写，这里的max中的两项当然就是当前状态的值了，为何？ 因为每种背包都是无限的。当我们把i从1到N循环时，fv表示容量为v在前i种背包时所得的价值，这里我们要添加的不是前一个背包，而是当前背包。所以我们要考虑的当然是当前状态。,完全背包 CompletePack,CompletePack,hdu1114,Sample Input
5、 3 10 110 2 1 1 30 50 10 110 2 1 1 50 30 1 6 2 10 3 20 4 Sample Output The minimum amount of money in the piggy-bank is 60. The minimum amount of money in the piggy-bank is 100. This is impossible.,多重背包 MultiplePack,for (i = 1; i = V) CompletePack(costi, weighti); return; int k = 1; while (k amounti) ZeroOnePack(k*costi, k*weighti); amounti = amounti - k; k = k*2; ZeroOnePack(amounti*costi, amounti*weighti); ,多重背包 MultiplePack,混合背包 MixedPack,for i=1N if /第i件物品属于01背包 ZeroOnePack(ci,wi) else if /第i件物品属于完全背包 CompletePack(ci,wi) else if /第i件物品属于多重背包 MultiplePack(ci,wi,ni),有依赖背包,二维费用背包,分组背包,
