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

北京工业大学2014在职工程硕士算法分析与设计上机题 ——广义背包（General Knapsack Problem）问题 第1页 共NUMPAGES11页 2014在职工程硕士算法分析与设计 广义背包问题实验报告 实 验 名 称： 用动态规划方法求解广义背包问题 实验小组成员： 实 验 时 间： 2014年10月 报告完成时间: 2014年11月 用动态规划方法解决广义背包GKP问题 基于对动态规划方法的了解，我们将采用动态规划的方法解决广义背包问题GKP(General Knapsack Problem)。 一、问题描述 给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包多次或不装入（但不能仅装入物品的一部分） 二、数学描述转化 给定背包重量为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的取值范围是0≤xi≤Mwi,1≤i≤n ，n为正整数。 求装入背包中的最大价值，即需要选择合适的装入方式，使得装入背包中每种物品价值之和最大。第i个物品的总价值为其价值vi乘以放入次数xi,即xivi，对n中物品的总价值求和,并取最大值即为本题所需解决的问题。公式如下： maxi=1nxivi 代入取值范围整理得如下依赖条件： 三、递归公式 广义背包问题非常类似于0-1背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种 如果仍然按照解01背包时的思路，令m（i，j）表示从前 i 种物品选取若干放入一个容???为 j 的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程（递归公式）， mi,j=mi-1,j , 0≤j≤wimaxmi-1,j,mi-1,j-xiwi+xivi, 0≤xiwi≤j 其边界条件为： 0, 0≤jwnvnxn, jwnxn 第一个式子表明: 如果第i种物品的重量大于背包的容量,则装入前i种物品得到的最大价值和装入前i-1种物品得到的最大值是相同的,即物品i不能装入背包; 第二个式子表明:如果第i种物品的重量小于背包容量,则会有以下两种情况: 1.如果把第i种物品装入背包,则背包中物品的价值等于把前i-1种物品装入容量为j-xiwi的背包的价值加上第i种物品的价值xiwi。 2.如果第i种物品没有装入背包，则背包中物品的价值就等于把前面i-1种物品装入容量为j的背包中所取得的价值。 显然，取二者中价值大者作为把前i种物品装入容量为j的背包中的最优解。 四、时间复杂度 这跟0-1背包问题一样有O(MN)个状态需要求解，但因为多了一个参数x，求解每个状态的时间则不是常数了，需在原有0-1背包问题的基础上加一层数量的循环,伪代码如下： for i=1…N? for j=0..M ? for(x=0;x*w[i] =j;x++) ? m[i][j]=max{m[i-1][j],m[i-1][j-x*w[i]]+x*v[i]} 求解状态m[i][j]的时间是 O(jwi) 那么总的时间复杂度就是 O(MN*Mwi) 五、算法实现 1. 算法优化 因为同一件物品可以选取多次，那么可以通过计算每件物品的单位价值，来优先放进单价最高的物品。这个优化的正确性显然：任何情况下都可将价值小重量用高得a换成物美价廉的b，得到至少不会更差的方案。 这里可以用快速排序的方法对物品进行单价排序，时间复杂度为O(N^2) 另外，针对背包问题而言，比较不错的一种方法是：首先将重量大于M的物品去掉，然后使用类似计数排序的做法案，计算出重量相同的物品中价值最