《0019算法笔记——【动态规划】0-1背包问题》由会员分享，可在线阅读，更多相关《0019算法笔记——【动态规划】0-1背包问题（12页珍藏版）》请在金锄头文库上搜索。
1、0019算法笔记 【动态规划】0-1 背包问题1、问题描述 ：给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为 vi，背包的容量为 C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定 c 0, wi 0, vi 0 , 1in.要求找一 n 元向量(x1,x2,xn,), xi0,1, wi xic,且 vi xi 达最大. 即一个特殊的整数规划问题。2、最优性原理 ：设 (y1,y2,yn)是 (3.4.1)的一个最优解. 则 (y2,yn)是下面相应子问题的一个最优解:证明 :使用反证法。若不然, 设(z2,z3,zn)是上述子问题的一个最优解,
2、而(y2,y3,yn)不是它的最优解。显然有 vizi viyi (i=2,n)且 w1y1+ wizi viyi, (i=1,n) 说明 (y1,z2, z3,zn)是(3.4.1)0-1 背包问题的一个更优解,导出(y1,y2,yn)不是背包问题的最优解, 矛盾。3、递推关系 ：设所给 0-1 背包问题的子问题的最优值为 m(i，j)，即 m(i，j)是背包容量为 j，可选择物品为i，i+1，n 时 0-1 背包问题的最优值。由 0-1 背包问题的最优子结构性质，可以建立计算 m(i，j)的递归式:注 :(3.4.3)式此时背包容量为 j，可选择物品为 i。此时在对 xi 作出决策之后,问
3、题处于两种状态之一:(1)背包剩余容量是 j,没产生任何效益； (2)剩余容量 j-wi,效益值增长了 vi ；算法 具体代码如下：cpp view plain copy1. /3d10-1 动态规划 背包问题 2. #include stdafx.h 3. #include 4. using namespace std; 5. 6. const int N = 4; 7. 8. void Knapsack(int v,int w,int c,int n,int m10); 9. void Traceback(int m10,int w,int c,int n,int x); 10. 11.
4、int main() 12. 13. int c=8; 14. int v=0,2,1,4,3,w=0,1,4,2,3;/下标从 1 开始 15. int xN+1; 16. int m1010; 17. 18. cout1; i-) 64. 65. jMax = min(wi-1,c); 66. for(int j=0; jc 72. 73. mij = max(mi+1j,mi+1j-wi+vi);/效益值增长 vi 74. 75. 76. m1c = m2c; 77. if(c=w1) 78. 79. m1c = max(m1c,m2c-w1+v1); 80. 81. 82. 83. /
5、x数组存储对应物品 0-1 向量,0 不装入背包，1 表示装入背包 84. void Traceback(int m10,int w,int c,int n,int x) 85. 86. for(int i=1; i2n 时，算法需要 (n2n)计算时间。4、算法的改进 ：由 m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1in)，函数 m(i,j)是关于变量 j 的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数 m(i,j)由其全部跳跃点唯一确定。如图所示。对每一个确定的 i(1in)，用一个表 pi存储函数 m(i，j)的全部跳跃点。表 pi可依计算
6、m(i，j) 的递归式递归地由表 pi+1计算，初始时pn+1=(0，0)。 一个例子：n=3，c=6，w=4，3，2，v=5 ，2，1。 函数 m(i,j)是由函数 m(i+1,j)与函数 m(i+1,j-wi)+vi 作 max 运算得到的。因此，函数 m(i,j)的全部跳跃点包含于函数 m(i+1，j)的跳跃点集pi+1与函数 m(i+1，j-wi)+vi 的跳跃点集 qi+1的并集中。易知，(s,t)qi+1当且仅当 wi=a 且 d 4. using namespace std; 5. 6. const int N = 4; 7. 8. template 9. int Knapsac
7、k(int n,Type c,Type v,Type w,int *p,int x); 10. template 11. void Traceback(int n,Type w,Type v,Type *p,int *head,int x); 12. 13. int main() 14. 15. int c=8; 16. int v=0,2,1,4,3,w=0,1,4,2,3;/下标从 1 开始 17. int xN+1; 18. 19. int *p = new int *50; 20. for(int i=0;i 62. int Knapsack(int n,Type c,Type v,T
8、ype w,int *p,int x) 63. 64. int *head = new intn+2; 65. headn+1=0; 66. 67. p00=0;/p0存储物品重量 68. p01=0;/p1存储物品价值，物品 n 的跳跃点（ 0，0） 69. 70. / left 指向 pi+1的第一个跳跃点，right 指向最后一个 71. /拿书上的例子来说，若计算 p3=0;则 left 指向 p4的第一跳跃点（0 0）right 指向（9,10） 72. int left = 0,right = 0,next = 1;/next 即下一个跳跃点要存放的位置 73. headn=1;/
9、headn用来指向第 n 个物品第一个跳跃点的位置 74. 75. for(int i=n; i=1; i-) 76. 77. int k = left;/k 指向 p 中跳跃点,移动 k 来判断 p与 p+（w v）中的受控点 78. for(int j=left; jc) break;/剩余的空间不能再装入 i，退出 for 循环; 81. Type y = pj0 + wi,m = pj1 + vi;/计算 p +（w v） 82. 83. /若 pk0较小则(pk0 pk1)一定不是受控点，将其作为 pi的跳跃点存储 84. while(k=y 且 m =pk1,判断是不是当前 i 的
10、最后一个跳跃点的受控点 101. /若不是则为 i 的跳跃点存储 102. if(mpnext-11) 103. 104. pnext0=y; 105. pnext+1=m; 106. 107. 108. /若是，则对下一个元素进行判断。 109. while(k 134. void Traceback(int n,Type w,Type v,Type *p,int *head,int x) 135. 136. /初始化 j,m 为最后一个跳跃点对应的第 0 列及第 1 列 137. /如上例求出的 最后一个跳跃点为（8 15）j=8,m=15 138. Type j = phead0-10,
11、m=phead0-11; 139. for(int i=1; i=n; i+) 140. 141. xi=0;/ 初始化数组； 142. for(int k=headi+1; k=headi-1;k+)/ 初始 k 指向 p2的第一个跳跃点（0 0） 143. 144. /判断物品 i 是否装入，如上例与跳跃点(6 9)相加等于（8 15）所以 1 装入145. if(pk0+wi=j & pk1+vi=m) 146. 147. xi=1;/物品 i 被装入，则 xi置 1 148. j=pk0;/ j 和 m 值置为满足 if 条件的跳跃点对应的值 149. m=pk1;/ 如上例 j=6,
12、m=9 150. break;/再接着判断下一个物品 151. 152. 153. 154. 上述算法的主要计算量在于计算跳跃点集 pi(1in)。由于 qi+1=pi+1(wi，vi)，故计算 qi+1需要 O(|pi+1|)计算时间。合并 pi+1和 qi+1并清除受控跳跃点也需要 O(|pi+1|)计算时间。从跳跃点集 pi的定义可以看出，pi中的跳跃点相应于 xi,xn 的 0/1 赋值。因此，pi中跳跃点个数不超过 2(n-i+1)。由此可见，算法计算跳跃点集 pi所花费的计算时间为 从而，改进后算法的计算时间复杂性为 O(2n)。当所给物品的重量 wi(1in)是整数时，|pi|c+1，(1in)。在这种情况下，改进后算法的计算时间复杂性为 O(minnc,2n)。运行结果如图：
