- 相关推荐
用动态规划法与回溯法实现0-1背包问题的比较
1背包问题0-1背包问题：给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。问应如何选择装入背包中物品，使得装入背包中物品的总价值最大？
对于一个实例：物品种类N=4，背包容量C=10，物品重量数组W={3，5，2，1}，相应价值数组V={9，10，7，4}。找一个n元0-1向量（x1，x2，x3….xn）xi∈{0,1},1≤i≤n.使得
，
达到最大。下面分别以动态规划法和回溯法来解决这个实例。
2动态规划法
动态规划法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。用一个表来保存记录所有已解决的子问题的答案，在需要的时候再找出已求得的答案，避免重复的计算。
动态规划法适用于解最优化问题。通常可按以下4个步骤：
(1)找出最优解的性质并刻画其结构特征。
(2)递归的定义最优解。
(3)以自底向上的方式计算出最优值。
(4)根据计算最优值时到得的信息，构造最优解。
对于所给0-1背包问题的子问题：
，
的最优值为m（i，j），即m（i，j）是背包容量为j，可悬着物品为i,i+1,….,n时0-1背包问题的最优值。由于0-1背包问题的最优子结构性质，可以建立计算m（i，j）的如下递归式：
（1.1）
（1.2）
从上面算法的执行过程中可以看出假设有Q（n）个子问题,每一个子问题最多需要m次决策,则计算的频率为nm,回溯的频率为n，那么整个过程的算法的时间复杂度为T（n）=nm+n，即为Q（nm）。
3回溯法。
回溯法在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。回溯算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。简单地说就是确定解空间,建立解空间树,用深度优先搜索算法递归搜索解空间树,并同时注意剪枝。
用回溯法解题的步骤：
(1)针对所给问题定义问题的解空间；
(2)确定易于搜索的解空间结构；
(3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效的搜索。
根据上述0-1背包问题的数学描述解向量可以表示成X={X,X,...X|X=0或=1}若X=0,表示第i个物品不装入背包，X=1，表示将第i个物品装入背包。
可以用树的形式将解空间表达出来。树中从第i层到第i+1层的边上的值表示解向量中X的取值，并假定第i层的左子树描述第i个物品被装入背包的情况，右子树描述第i个物品被拒绝的情况。则该0-1背包问题的状态空间树就表示为一棵高度为n的完全二叉树。若n=3时则此0-1背包问题的解空间的结构如图1-1所示。从根结点到叶子结点的任一路径就对应解空间中的一个解向量
图1-1n=3时，0-1背包问题的解空间树
用回溯法求解0-1背包问题时，可以按照物品的单位价值从大到小排序。计算当前节点的上界,搜索左子树。只有当右子树包含可行解时才搜索右子树。剪去右子树的条件是当前价值加上剩余物品的总价值小于当前的最优总价值时,不需搜索右子树,可将右子树剪去。回溯法用一定的剪枝进行优化,算法的时间复杂度为O(n*2n),n为物品个数。
4总结
动态规划算法：动态规划可以把困难得多阶段决策变换为一系列相互联系比较容易的单阶段问题。对于背包问题可以对子过程用枚举法求解,而且约束条件越多,决策的搜索范围越小,求解也越容易。但是对于规模较大的问题它并不是一个理想的算法。最重要的原因就是它的维数障碍。即计算和存储量的需要对于状态空间和决策空间的维数的增长呈指数增长关系，这样惊人的增长速度是计算机难以承受的。这就使得直接的动态规划方法求解规划较大的背包问题发生了困难，且目前尚没有好的解决办法。
回溯法：回溯法需要为问题定义一个解空间,这个解空间必须至少包含问题的一个解(可能是最优的)。使用递归回溯法解决背包问题的优点在于它算法思想简单,而且它能完全遍历搜索空间,肯定能找到问题的最优解。但是由于此问题解的总组合数有2个,因此,随着物件数n的增大,其解的空间将以2级增长,当n大到一定程度上,用此算法解决背包问题将是不现实的。
用此两种方法都能得到问题的最优解，从其时间复杂度来看，两者的速度都较慢。
【用动态规划法与回溯法实现0-1背包问题的比较】相关文章：
比较的特殊表达法初探01-08
比较法楷书教学探索02-25
“听说法”与“交际法”的比较及启示08-17
比较法在物理中的应用08-17
欧美产品责任法比较及启示02-20
儒法之比较及其现代意义02-24
运用改换比较法培养语感08-17
国际法与国内法关系中日之比较02-20
产品责任法相关问题比较11-18