01背包问题
一、问题描述与分析
经常遇到一些复杂的问题，有时我们将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。由于分解到的子问题往往不是独立的，用一个表来记录所有已解决的子问题的答案，这样就得到了原问题的解，这就是动态规划法的基本思想。回溯法有“通用解题法”之称。它可以系统地搜索问题的所有解。回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。这种以深度优先方式搜索问题解的算法称为回溯法。01背包问题：给定
种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问：应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？
二、算法设计
1设所给01背包问题的子问题max

ki


vkxk
wkxkjki和x的最有值为mij的背包容量为k01ik


j，可选择物品为ii1
时01背包问题的最优值。由01背包问题的最优子结构性质，可以建立如下计算mij的递归式：
mij

maxmi1jmi1jwivijwimi1j0jwiv
jw
00jw

m
j
2
此方法为动态规划解01背包问题。01背包问题是子集选取问题。一般情况下，01背包问题是NP难的。01背包问题的解空间可用子集树表示。解01背包问题的回溯法与装载问题的回溯法十分相似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树有可能最优解时才进入右子树搜索；否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cpr≤bestp时，可剪去右子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，由此得到的价值是右子树中解的上界。此方法为回溯法解01背包问题。
三、得出算法：
1．动态规划解01背包算法：VoidK
apSacki
t
i
twi
tvi
txi
tCi
tijfori0i
iVi00
fforj0jCjV0j0fori0i
r