动态规划的基本思路：
动态规划算法通常被用于求解具有某些最优性质的问题，也就是我们平时所说的最优子结构的性质。
动态规划算法与分割统治法相似，其基本思路是将需要求解的问题分解为几个子问题，先求解子问题，再从这些子问题的解中得到原问题的解。 与分割统治法最大的不同在于，适合用动态规划求解的问题，但分解得到的部分问题往往不相互独立，即下一部分阶段的解基于前一部分阶段的解进一步求解。
用分割统治法解决这样的问题的话，分解得到的部分问题数量太多，有些部分问题会被多次计算出来。 如果能够保存已解决的子问题的答案并根据需要找到所需的答案，则可以避免大量的重复计算，从而节约时间。 我们可以用一个表记录所有解开的子问题的答案。 不管这个子问题今后是否被使用，如果计算出来的话，将其结果记入表中。
问题说明：
请给我一个n里的东西和一个背包。 物I的重量为Wi，其价值为Vi，背包的容量为c。 为了使放在背包里的东西的总价值最大化，应该怎么选择放在背包里的东西？
在选择物品时，每个物品I只有放入或不放入背包两个选择。 不能多次放物品I，也不能只放物品的一部分。 因此，这个问题被称为0-1背包问题。
问题分析：最初的I(1=I=n )个物品中，j ) j(1=j=C )可以放入背包的物品的最大价值表示为v ) I，j )，则以下动态规划函数：(1) v ) I，
(2) a ) v ) I，j )=v ) I-1，j ) j
(b ) v ) I，j )=max ) v(I-1，j )，v ) I-1，j-wi ) vi ) ) jwi
)式表示，第I个物品的重量大于背包的容量时，放人前面第I个物品得到的最大价值与放前面第i-1个物品得到的最大价格相同，即物品I不能放入背包。
)如果第I项的重量小于背包的容量，则表达式(a )如果第I项没有放在背包中，则背包中的项的价值与将第一个i-1项放在容量为j的背包中获得的价值相同(b )将第I个物品放入背包时，背包物品的价值明显等于第i-1个物品放入容量位j-wi的背包的价值加上第I个物品的价值vi，作为将前I个物品放入容量j的背包的最佳解
推荐教程： PHP教程