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

2014在职工程硕士算法分析与设计广义背包问题实验报告实验名称：用动态规划方法求解广义背包问题实验小组成员：实验时间：2014年10月报告完成时间:2014年11月北京工业大学2014在职工程硕士算法分析与设计上机题——广义背包（GeneralKnapsackProblem）问题第1页共11页用动态规划方法解决广义背包GKP问题基于对动态规划方法的了解，我们将采用动态规划的方法解决广义背包问题GKP(GeneralKnapsackProblem)。一、问题描述给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包多次或不装入（但不能仅装入物品的一部分）二、数学描述转化给定背包重量为M0;给定n中物品其重量分别为w1,w2,w3,……wn;n种物品对应的价值为v1,v2,v3,……vn；设xi为第i种物品装入背包的数量；若第i种物品不装入则𝒙𝒊取值为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为正整数。北京工业大学2014在职工程硕士算法分析与设计上机题——广义背包（GeneralKnapsackProblem）问题第1页共11页求装入背包中的最大价值，即需要选择合适的装入方式，使得装入背包中每种物品价值之和最大。第i个物品的总价值为其价值vi乘以放入次数xi,即xivi，对n中物品的总价值求和,并取最大值即为本题所需解决的问题。公式如下：𝒎𝒂𝒙∑𝒙𝒊𝒏𝒊=𝟏𝒗𝒊代入取值范围整理得如下依赖条件：三、递归公式广义背包问题非常类似于0-1背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种如果仍然按照解01背包时的思路，令m（i，j）表示从前i种物品选取若干放入一个容量为j的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程（递归公式），m(i,j)={m(i−1,j),0≤j≤wimax{m(i−1,j),m(i−1,j−xiwi)+xivi},0≤xiwi≤j其边界条件为：{0,0≤jwnvnxn,jwnxn第一个式子表明:如果第i种物品的重量大于背包的容量,则装入前i种物品北京工业大学2014在职工程硕士算法分析与设计上机题——广义背包（GeneralKnapsackProblem）问题第1页共11页得到的最大价值和装入前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背包问题的基础上加一层数量的循环,伪代码如下：fori=1…Nforj=0..Mfor(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)北京工业大学2014在职工程硕士算法分析与设计上机题——广义背包（GeneralKnapsackProblem）问题第1页共11页那么总的时间复杂度就是O(MN∗∑Mwi)五、算法实现1.算法优化因为同一件物品可以选取多次，那么可以通过计算每件物品的单位价值，来优先放进单价最高的物品。这个优化的正确性显然：任何情况下都可将价值小重量用高得a换成物美价廉的b，得到至少不会更差的方案。这里可以用快速排序的方法对物品进行单价排序，时间复杂度为O(N^2)另外，针对背包问题而言，比较不错的一种方法是：首先将重量大于M的物品去掉，然后使用类似计数排序的做法案，计算出重量相同的物品中价值最高的是哪个，可以O(V+N)地完成这个优化。2.运行结果默认数据来自于算法教材（第三版）133页的示例，我们运行结果是物品4装入7次总价值等于28北京工业大学2014在职工程硕士算法分析与设计上机题——广义背包（GeneralKnapsackProblem）问题第1页共11页我们实现充分考虑到测试算法各细节的需要，可以修改已有物品的重量和价值，然后重新计算出新的结果，如下图所示根据算法教材（第三版）133页的示例数据，将物品3的价值从7修改为13，可得出新的装入方案即物品3装入3次，物品4装入1次，总价值3*13+1*4=43除此之外，我们的实现还可以随机生成物品种类，修改各参数，如下图所示，随机生成5种物品，修改部分价值，按照背包容量为11，计算出新的装入方案：物品1装入1次，物品3装入2次，物品5装入1次，总价值1012。北京工业大学2014在职工程硕士算法分析与设计上机题——广义背包（GeneralKnapsackProblem）问题第1页共11页北京工业大学2014在职工程硕士算法分析与设计上机题——广义背包（GeneralKnapsackProblem）问题第1页共11页3.相关代码动态规划部分代码北京工业大学2014在职工程硕士算法分析与设计上机题——广义背包（GeneralKnapsackProblem）问题第1页共11页北京工业大学2014在职工程硕士算法分析与设计上机题——广义背包（GeneralKnapsackProblem）问题第1页共11页快速排序算法源码北京工业大学2014在职工程硕士算法分析与设计上机题——广义背包（GeneralKnapsackProblem）问题第1页共11页attachedotherinfo广义背包问题new.pptx