对于一个实例：物品种类N=4，背包容量C=10，物品重量数组W={3，5，2，1}，相应价值数组V={9，10，7，4}。 以下就是由精品学习网为您提供的用动态规划法与回溯法实现0-1背包问题。
找一个n元0-1向量(x1，x2，x3….xn)xi∈{0,1},1≤i≤n.使得
，
达到最大。下面分别以动态规划法和回溯法来解决这个实例。
2动态规划法
动态规划法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。用一个表来保存记录所有已解决的子问题的答案，在需要的时候再找出已求得的答案，避免重复的计算。
动态规划法适用于解最优化问题。通常可按以下4个步骤：
(1)找出最优解的性质并刻画其结构特征。
(2)递归的定义最优解。
(3)以自底向上的方式计算出最优值。
相关推荐：
下一篇：用WORD制作电子贺卡论文
