动态规划与回溯法解决0-1背包问题

《动态规划与回溯法解决0-1背包问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.0-1背包动态规划解决问题一、问题描述：有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？二、总体思路：根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。三、动态规划的原理及过程：number＝4，capacity＝7i1234w(重量)3521v(价值)91074原理：　　动态规划与分治法类似，都是把大问题拆分成小问题，通

2、过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。过程：　a) 把背包问题抽象化（X1，X2，…，Xn，其中Xi取0或1，表示第i个物品选或不选），Vi表示第i个物品的价值，Wi表示第i个

3、物品的体积（重量）；　　b) 建立模型，即求max(V1X1+V2X2+…+VnXn)；　　c) 约束条件，W1X1+W2X2+…+WnXn

4、n)是01背包问题的最优解，则有(X2，X3，…，Xn)是其子问题的最优解，　　　　假设(Y2，Y3，…，Yn)是上述问题的子问题最优解，则理应有(V2Y2+V3Y3+…+VnYn)+V1X1 >(V2X2+V3X3+…+VnXn)+V1X1；..　　　　而(V2X2+V3X3+…+VnXn)+V1X1=(V1X1+V2X2+…+VnXn)，则有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V1X1+V2X2+…+VnXn)；　　　　该式子说明(X1，Y2，Y3，…，Yn)才是该01背包问题的最优

5、解，这与最开始的假设(X1，X2，…，Xn)是01背包问题的最优解相矛盾，故01背包问题满足最优性原理；　　f) 寻找递推关系式，面对当前商品有两种可能性：　　　　第一，包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；　　　　第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝　　　　　　　其中V(i-1,j)表示不装，V(

6、i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)但价值增加了v(i)；　　　　由此可以得出递推关系式：　　　　1) j=w(i)    V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝number＝4，capacity＝7i1234w(重量)3521v(价值)91074四、构造最优解：最优解的构造可根据C列的数据来构造最优解，构造时从第一个物品开始。从i=1,j=c即m[1][c

7、]开始。　　　　1、对于m[i][j]，如果m[i][j]==m[i+1][j]，则物品i没有装入背包，否则物品i装入背包；　 2、为了确定后继即物品i+1，应该寻找新的j值作为参照。如果物品i已放入背包，则j=j-w[i]；如果物品i未放入背包，则j=j。　　3、重复上述两步判断后续物品i到物品n-1是否放入背包。　　4、对于物品n，直接通过m[n][j]是否为0来判断物品n是否放入背包。只要能通过找规律手工填写出上面这张表就算理解了01背包的动态规划算法。首先要明确这张表是至底向上，从左到右生成的。.

8、.序号WeightValue123456713947111316202025104711111114173274711111111114144444444从表格中可以看出背包的最大价值value=20，即当X1=1，X2=0，X3=1，X4=1。五、算法测试代码：#include#include#include#include#include