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

1、火Ex亭2014在职工程硕士算法分析与设计广义背包问题实验报告实验名称：用动魏a划方法求解广义背包问题蒲小眦员:实验时间：2014年10月报告完成时间：2014年11月北京工业大学2014在职工程硕士算法分析与设计上机题 广义背包(General Knapsack Problem )问题 用动态规划方法解决广义背包GKP问题基于对动态规划方法的了解，我们将采用动态规划的方法解决广义背包问题GKP(General Knapsack Problem)。问题描述给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在 需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的 物

2、品的总价值最大化。规则是，每种物品均可装入背包多次或不装入(但不能仅 装入物品的一部分)二数学描述碱给定背包重量为M0;给定n中物品其重量分别为W1，W2，W3,Wn;n种物品对应的价值为vi，v2f v3fvn ;设为为篥i种物品装入背包的数量；若篥i种物品不装入则由取值为0；有题目给定可知，物品可反复装入，即均可取 1,2,3.,但由于背包的总容量为M,所以第i种物品装入背包的次数X应当满足如 下条件吗况 M,即篥i种物品的总重量(篥i种物品单个的重量Wj乘以放入的 次i数g)应当小于总容量,否则无法放入，另外由于题目给定不能仅装入某物品的 一部分可知放入次数为必须为整数。因此可得为的取值

3、范围是0 Xili1(由雄式九1，=，MI 0 i n三、递归公式广义背包问题非常类似于0-1背包问题，所不同的是每种物品有无限件。也 就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0 件、取1件、取2件.等很多种如果仍然按照解01背包时的思路，令m(ij)表示从前i种物品选取若 干放入一个容量为j的背包的最大权值。仍然可以按照每种物品不同的策略写 出状态转移方程(递归公式)，广.)=j m(i- l,j),0 j Wim L J (max(m(i - 1, j), m(i - 1J - XjWj) + x, 0 XjWj j其边界条件为:(0f 0 j WnXn篥一个式

4、子表明：如果第i种物品的重量大于背包的容量，则装入前i种物品得到的最大价值和装入前i-l种物品得到的最大值是相同的,即物品i不能装入背篥二个式子表明:如果篥i种物品的重量小于背包容量,则会有以下两种情况:L如果把第i种物品装入背包，则背包中物品的价值等于把前i-l种物品装入 容量为j -XiWi的背包的价值加上第i种物品的价值XjWi。2.如果篥i种物品没有装入背包，则背包中物品的价值就等于把前面i-l种 物品装入容量为J的背包中所取得的价值。显然取二者中价值大者作为把前i种物品装入容量为j的背包中的最优解。,时间复杂度这跟0-1背包问题一样有O(MN)个状态需要求解但因为多了一个参数x, 求

5、解每个状态的时间则不是常数了需在原有0-1背包问题的基础上加一层数量 的循环，伪代码如下：for i = Nfor j=0.M for(x=0;x*wi v=j；x+)mij=maxmi-lj,mi-lj-x*wi+x*vi求解状态mij的时间是那么总的时间复杂度就是ZM五，算法实现1.算法优化因为同一m勿品可以选取多次，那么可以通过计算每件物品的单位价值，来 优先放进单价最高的物品。这个优化的正确性显然：田可情况下都可阁介值小重 量用高得a换成物美价廉的b，得到至少不会更差的方案。这里可以用快速排序的方法对物品进行单价排序，时间复杂度为0(N2)另外，针对背包问题而言，比较不错的一种方法是：

6、首先将重量大于M的 物品去掉，然后使用类似计数排序的做法案，计算出重量相同的物品中价值最高 的是哪个，可以O(V+N)地完成这个优化。2.运行结果默认数据来自于算法教材(篥三版)133页的示例，我们运行结果是物品 4装入7次总价值等于28我们实现充分考虑到测试算法各细节的需要,可以修改已有物品的重量和价 值，然后重新计算出新的结果，如下图所示根据算法教材(篥三版)133页的示 例数据，将物品3的价值从7修改为13 ,可得出新的装入方案即物品3装入3 次，物品4装入1次，总价值3*13+1*4=43除此之外我们的实现还可以随机生成物品种类修改各参数，如下图所示, 随机生成5种物品，修改部分价值，

7、按照背包容量为11 ,计算出新的装入方案: 物品1装入1次，物品3装入2次，物品5装入1次，总价值1012o北京工业大学2014在职工程硕士算法分析与设计上机题3.相关代码动态规划部分代码/ Kparan nae=-tLis-t排好序的物品清单，单价从低到高/ Kparajii 11孙自=，。槌/背包总答照。pa匚邱/ 不放入的单勺更高的物品数里/ J 史最高总价。paramprivate void Algo r it hm (Ar r ayL 1st tList, int total, int *t op, int o Idiot al) if (hasMax)/记录是否已经找到最优选择初始

8、化为0return;int tv = 0;int left = tot al;for (int i = 1: i old!otal)当前总作值超过之前的方案oldTotal = tv;resutIList = new ArrayList(tList):tList = new ArrayList (tOldList):Algorithm(tList, -total, +top3 tv);elseif (top = tList.Count)return;之前方案更好tList = new ArrayList (tOldList);Algorithm(tList, *total, +top, old

9、Total):firegion装入第i个物品tmp. n = left / tmp.w; left = left % tmp.w;tv += tmp. n * tmp.v;tList tList. Count - i - top = tmp;if (left = 0)break;Sendregion快速排序算法源码region快速排序定位private int Part it ion (ref ArrayLisl List5 int loWj int high)|int i = low;int j = high;object keyObj = list low:double key = (El

10、ement)list lo-ur). pv;while (i key 炭& j i)一一 j：list i = list j;while (Elemerrt)list i) .pv i)+i；= list i;list i = keyObj;return j：快速排序private void QSort(ref ArrayList list, int low, int high)if (Low high)int q = Part it ion (ref listj Low, high):QSort (ref list, low。 q - 1);QSort (ref list, q + high):private void QSort (ref ArrayList list)this. QSort (ref list5 0, list. Count - 1):#endreg:ion13 14 15 16 17 36 37 44 45 51 52 66 67 lly 120 181 182 252 253 260 261 299 300 350 351 369 370 557 558 606 607 608 609-namespace hnap sackPr ob LemS田.publ