广义背包报告

1、广义背包问题一，问题描述 给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包多次或不装入（但不能仅装入物品的一部分）。二，数学描述给定背包载重量M 0，物品重量wi 0，物品价值vi 0，其中1in，要求找出n元向量(x1, x2, . , xn)，xiN，1in，使得而且达到最大。三，边界条件 ，其中xiN，1in四，递归关系设广义背包子问题的最优值为m(i, j)，即m(i, j)是背包载重量为j，可选物品为i, i+1, . , n时广义背包问题的最优值。m

2、(i, j)的递归式五，算法分析由m(i, j)的递归式容易证明，对每个确定的i (1in)，函数m(i, j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。即函数m(i, j)由其全部跳跃点唯一确定。注意到计算m(i, j)的递归式在变量j是连续变量，可以对每一个确定的i (1in)，用一个表pi存储函数m(i, j)的全部跳跃点。对每一个确定的实数j，可以通过查找表pi确定函数m(i, j)的值。Pi的全部跳跃点(j, m(i, j)依j的升序排列。由于函数m(i, j)是关于变量j的阶梯状单调不减函数，故pi中全部跳跃点的m(i, j)值也是递增排列的。表pi可依计算m

3、(i, j)的递归式递归地由表pi-1计算，初始时pi-1 = p0 = (0, 0)。事实上函数m(i, j)是由函数m(i - 1, j)与函数m(i, j - wi) + vi做max运算得到的。因此，函数m(i, j)的全部跳跃点包含于函数m(i - 1, j)的跳跃点集pi-1与函数m(i, j - wi) + vi的跳跃点集qi的并集中。易知(s, t)qi当且仅当wisM且(s - wi, t - vi)pi。因此，容易由pi确定跳跃点集qi如下：qi = pi(wi, vi) = (j + wi, m(i, j) + vi) | (j, m(i, j)pi 值得注意的是，上式中

4、的pi是由pi-1qi 得到的。在算法实现时设定pi初值为(0, 0)，由此逐步计算qi以及pi的后续值。另一方面，设(a, b)和(c, d)是pi-1qi 中的两个跳跃点，则当ca且d b时，(c, d)受控于(a, b)，即(c, d)不是pi中的跳跃点。除受控点外，pi-1qi 中的其他跳跃点均为pi的跳跃点。由此可见，在递归地由表pi-1计算表pi时，可先由初始值pi = (0, 0)逐步计算qi，然后合并表pi-1和qi，并清除其中的受控点得到表pi的后续值，如此反复。六，算法实现广义背包的标记函数动态规划算法实现如下：public static int kanpsack(doub

5、le w, double v, double M, Good p) / w存放各物品重量，v存放各物品价值，M为背包载重，p为跳转表int n = w.length - 1; / 物品总数int right = 0; / 右指针，指向遍历区间尾部int left = 0; / 左指针，指向遍历区间头部int next = 1; / 节点指针，指向下一个待遍历的节点for (int i = 1; i = n; i+) / 遍历所有物品int k = left;for (int j = right + 1; pj.getWei() + wi = M; j+) / 遍历当前物品的跳转表/ 对前一个跳

6、转表中的每一个值加上当前物品的weight和valueint id = i;double weight = pj.getWei() + wi;double value = pj.getVal() + vi;while (k = right & pk.getWei() weight) / 在介于pk到pk+wi之间的位置填入前一个跳转表中的数值pnext.setId(pk.getId();pnext.setWei(pk.getWei();pnext+.setVal(pk+.getVal();if (k = right & pk.getWei() = weight) / 重量相等情况/ 当遇到前一

7、个跳转表和pk+wi重量相等时，选取两者中价值较大者if (value pnext-1.getVal() / 当前的weight和value不是受控点的话，将其填入当前跳转表pnext.setId(id);pnext.setWei(weight);pnext+.setVal(value);while(k = right & pk.getVal() = pnext-1.getVal()/ k在前一个跳转表中移动到比当前节点value更大的节点处（也是删除受控点的过程），等待下一次填写k+;/ j+，对前一个跳转表中下一个值加上当前物品的weight和value循环以上方法while (k = r

8、ight) / j已遍历完，如果k指向更大的节点，将k填入当前跳转表最大项，即j没有选入背包pnext.setId(pk.getId();pnext.setWei(pk.getWei();pnext+.setVal(pk+.getVal();/ 当前跳转表已填完，转入下一个物品的跳转表left = right + 1;right = next - 1;return next - 1; / 返回最优值其中Good为自定义类，定义了物品属性：class Good private int id; / 物品编号private double val; / 物品价值private double wei;

9、/ 物品重量/ 构造函数及Getter and Setter略引入Good类方便了由最优值和跳转表构造最优解的过程，最优解函数如下：while (presult.getId() != 0) / result初值为最优值，按装入物品编号递减得到最优解System.out.print(presult.getId() + t);double temp = presult.getWei() - wpresult.getId();while (presult.getWei() != temp)result-;七，时间复杂度分析1，标记函数时间复杂度：标记函数的主要计算量在于计算跳转表。当物品重量均为整数时，对于任意跳转表pi至多包