资源描述：
《背包问题九讲和源程序(答案)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、背包问题九讲和源程序（答案）.txt台湾一FI不收复，我-円不过4级！如果太阳不出來了，我就不去上班了；如果出来了，我就继续睡觉！0录第一讲01背包14题这是菽木的背包问题，每个物品敁多只能放一次。第二讲完全竹包问题笫二个基本的背包问题模型，每种物品可以放无限多次。第三讲多重背包问题毎种物品有一个岡定的次数上限。第叫讲混合三种背乜
2、4题将前而三种简单的问题叠加成较S杂的问题。第五讲二维费用的背包问题一个简单的常见扩展。第六讲分组的背包M题一种题FI类型，也是一个有用的模型。f两节的®础。第七讲有依赖的
3、竹包问题另一利1给物品的选取加上限制的方法。第八讲泛化物品我白己关于背包问题的思考成果，有一点抽象。第九讲背包问题问法的变化试图触类旁通、举一反三。附：USAC0中的背包问题给出USACOTraining上可供练习的背包问题列表，及简单的解答。P01:01背包问题题R有N件物品和一个容量为V的竹包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入竹包可使价值总和最大。基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用了问题定义状态：即f[i][V]表示前i件物品
4、恰放入一个容呈为V的背包吋以获得的大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}这个方程非常重要，基本上所脊跟背包相关的问题的方程都足中它衍生出米的。所以有必要将它详细解释一下:“将前i件物品放入容跫为v的竹包屮”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容虽为v的竹包中”，价值为f[i-1][v];如果放第i件物品，那么问
5、题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背乜中”，此吋能获得的最大价值就是f[i_l][v_c[i]]再加上通过放入第i件物品获得的价值w[i]。优化空间复杂度以上方法的吋间和空闽复杂度均为O（N*V），其屮时阆复杂度基木己经不能再优化了，但空W复杂度却可以优化到0（V）。先考虑上而讲的基本思路如何实现，肯定是有一个主循环i=l..N,每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i
6、][v]呢？f[i][v]是由f[i-l][v]和f[i-l][v-c[i]]两个子问题递推而來，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[H][v]和f[i-l][v-c[i]]的值呢？事实上，这要求在毎次主循环屮我们以v=V..O的顺序推f[v],这样才能保证推f[v]时f[V-C[i]]保存的是状态f[i-l][V-C[i]]的值。伪代码如下:fori=l..Nforv二V..0f[v]=max{f[v],f[v-c[i]]+w[i]};其中的f[v]=max{
7、f[v],f[v-c[i]]}—句恰就相当于我们的转移力*程f[i][v]=max{f[i—1][v],f[i-1][v-c[i]]},因为现在的f[V-C[i]]就相当于原来的f[i-1][V-C[i]]。如果将V的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符,但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维数组解01竹包问题是十分必耍的。事实上，使用一维数组解01背包的程序在后而会被多次用到，所以这里抽象出一个处理-件01
8、背包中的物品过程，以后的代码中直接调用不加说明。过程ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值。procedureZeroOnePack(cost,weight)forv=V..costf[v]=max{f[v],f[v-cost]+weight}注意这个过程里的处现与前面给出的伪代码有所不同。前面的示例稈序写成v=V..0足为了在程序屮体现每个状态都按照尨程求解了，避免不必要的思维复杂度。而这里既然已经杣象成看作黑箱的过程了，就可
9、以加入优化。赀用为cost的物品不会影响状态f[0..cost-1],这是显然的。有了这个过程以后，01竹包问题的伪代码就4以这样写：fori=l..NZeroOnePack(c[i],w[i]);初始化的细节问题我们看到的求敁优解的背包问题题FI中，事实匕冇两种不太相同的问法。冇的题FI要求“恰好装满背包”时的敁优解，奋的题n则井没奋要求必须把背包装满。一种区别这两种问法的实现方法足在初始化的吋候奋所不同。如果是第一种问法，要求恰好装满背乜，那么在初始
