广义背包报告.doc

《广义背包报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、排列的。表p[i]可依计算m(i,j)的递归式递归地由表p[i-1]计算，初始时p[i-1]=p[0]={(0,0)}。事实上函数m(i,j)是由函数m(i-1,j)与函数m(i,j-wi)+vi做max运算得到的。因此，函数m(i,j)的全部跳跃点包含于函数m(i-1,j)的跳跃点集p[i-1]与函数m(i,j-wi)+vi的跳跃点集q[i]的并集中。易知(s,t)∈q[i]当且仅当wi≤s≤M且(s-wi,t-vi)∈p[i]。因此，容易由p[i]确定跳跃点集q[i]如下：q[i]=p[i]⊕(wi,vi)={(j+wi,m(i,j)+vi)

4、(j,m(i,j))∈p[i]}值

5、得注意的是，上式中的p[i]是由p[i-1]∪q[i]得到的。在算法实现时设定p[i]初值为{(0,0)}，由此逐步计算q[i]以及p[i]的后续值。另一方面，设(a,b)和(c,d)是p[i-1]∪q[i]中的两个跳跃点，则当c≥a且d

6、背包的标记函数动态规划算法实现如下：publicstaticintkanpsack(double[]w,double[]v,doubleM,Good[]p){//w[]存放各物品重量，v[]存放各物品价值，M为背包载重，p[]为跳转表intn=w.length-1;//物品总数intright=0;//右指针，指向遍历区间尾部intleft=0;//左指针，指向遍历区间头部intnext=1;//节点指针，指向下一个待遍历的节点for(inti=1;i<=n;i++){//遍历所有物品intk=left;for(intj=right+1;p[j].getWei()+w[i]<=M;

7、j++){//遍历当前物品的跳转表//对前一个跳转表中的每一个值加上当前物品的weight和valueintid=i;doubleweight=p[j].getWei()+w[i];doublevalue=p[j].getVal()+v[i];while(k<=right&&p[k].getWei()

8、=right&&p[k].getWei()==weight){//重量相等情况//当遇到前一个跳转表和p[k]+w[i]重量相等时，选取两者中价值较大者if(valuep[next-1].getVal()){//当前的weight和value不是受控点的话，将其填入当前跳转表p[next].se