在上一篇《背包问题 －－ 1) 思路，递归求解》中，我们讨论了用递归的方式来解决背包问题。但是，直接使用递归会造成大量的重复运算，就上一篇中的例子来说，对于容积为17的背包来说，其中两种组合方案为：
方案一： 4(A) + 5(B) = 9 ，即背包中装一个A物品和一个B物品；
方案二： 5(B) + 10(C) = 15 ，即背包中装一个B物品和一个C物品；
注意，上面两种方案都需要计算knap(space = cap - item[1].size)（注：1对应B物品）的情况，这就造成了重复计算，而且计算量是成指数增长的。如果我们在第一次计算knap(space = cap - item[1].size)时就保存其返回值，那么在下一次需要用到的时候只需要直接使用这个返回值就行了，而不必再去计算。
这里我们给出动态编程的定义，即递归程序中，在每一步递归调用前使用已计算的值来完成当前的递归调用。
对于背包问题，我们用一个数组knowKnap[M]来保存每一个可能的space值。按动态编程改进后的程序源代码如下：
