用动态规划方法求解广义背包问题 final

1、2014在职工程硕士算法分析与设计广义背包问题实验报告实 验 名 称： 用动态规划方法求解广义背包问题 实验小组成员： 实 验 时 间： 2014年10月 报告完成时间: 2014年11月 用动态规划方法解决广义背包GKP问题基于对动态规划方法的了解，我们将采用动态规划的方法解决广义背包问题GKP(General Knapsack Problem)。一、问题描述给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包多次或不装入（但不能仅装入物品的一部分）二、数学描述转

2、化给定背包重量为M0;给定n中物品其重量分别为w1,w2,w3,wn; n种物品对应的价值为v1,v2,v3,vn；设xi为第i种物品装入背包的数量；若第i种物品不装入则xi取值为0;有题目给定可知,物品可反复装入,即xi可取1,2,3.,但由于背包的总容量为M,所以第i种物品装入背包的次数xi应当满足如下条件wi*xi M,即第i种物品的总重量(第i种物品单个的重量wi乘以放入的次i数xi)应当小于总容量,否则无法放入,另外由于题目给定不能仅装入某物品的一部分可知放入次数xi必须为整数。因此可得xi的取值范围是0xiMwi,1in ，n为正整数。求装入背包中的最大价值，即需要选择合适的装入方

3、式，使得装入背包中每种物品价值之和最大。第i个物品的总价值为其价值vi乘以放入次数xi,即xivi，对n中物品的总价值求和,并取最大值即为本题所需解决的问题。公式如下：maxi=1nxivi代入取值范围整理得如下依赖条件：三、递归公式广义背包问题非常类似于0-1背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件等很多种如果仍然按照解01背包时的思路，令m（i，j）表示从前 i 种物品选取若干放入一个容量为 j 的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程（递归公式）， mi,j=mi-1,j ,

4、0jwimaxmi-1,j,mi-1,j-xiwi+xivi, 0xiwij 其边界条件为： 0, 0jwnxn第一个式子表明: 如果第i种物品的重量大于背包的容量,则装入前i种物品得到的最大价值和装入前i-1种物品得到的最大值是相同的,即物品i不能装入背包;第二个式子表明:如果第i种物品的重量小于背包容量,则会有以下两种情况:1.如果把第i种物品装入背包,则背包中物品的价值等于把前i-1种物品装入容量为j-xiwi的背包的价值加上第i种物品的价值xiwi。2.如果第i种物品没有装入背包，则背包中物品的价值就等于把前面i-1种物品装入容量为j的背包中所取得的价值。 显然，取二者中价值大者作为把

5、前i种物品装入容量为j的背包中的最优解。四、时间复杂度这跟0-1背包问题一样有O(MN)个状态需要求解，但因为多了一个参数x，求解每个状态的时间则不是常数了，需在原有0-1背包问题的基础上加一层数量的循环,伪代码如下： for i=1N for j=0.M for(x=0;x*wi =j;x+) mij=maxmi-1j,mi-1j-x*wi+x*vi 求解状态mij的时间是 O(jwi)那么总的时间复杂度就是 O(MN*Mwi)五、算法实现1. 算法优化因为同一件物品可以选取多次，那么可以通过计算每件物品的单位价值，来优先放进单价最高的物品。这个优化的正确性显然：任何情况下都可将价值小重量用

6、高得a换成物美价廉的b，得到至少不会更差的方案。 这里可以用快速排序的方法对物品进行单价排序，时间复杂度为O(N2)另外，针对背包问题而言，比较不错的一种方法是：首先将重量大于M的物品去掉，然后使用类似计数排序的做法案，计算出重量相同的物品中价值最高的是哪个，可以O(V+N)地完成这个优化。 2. 运行结果默认数据来自于算法教材（第三版）133页的示例， 我们运行结果是物品4装入7次总价值等于28我们实现充分考虑到测试算法各细节的需要，可以修改已有物品的重量和价值，然后重新计算出新的结果，如下图所示根据算法教材（第三版）133页的示例数据，将物品3的价值从7修改为13，可得出新的装入方案即物品3装入3次，物品4装入1次，总价值3*13+1*4=43除此之外，我们的实现还可以随机生成物品种类，修改各参数，如下图所示，随机生成5种物品，修改部