动态规划——背包问题

背包问题的本质:

如果每件物品都要考虑是否放入背包所需的深度为n，最坏就需要O()的时间

而在考虑每件物品的过程中，中间有很多分支的计算是重复的，或者说可以基于之前的运算得到的子问题答案简化本次的运算量

因此空间换时间，开一个数组记录中间的运算过程，得到答案。

先展示一下原始时间复杂度比较差的思路：

不管如何，用测试数据也能返回正确结果。

接下来使用动态规划，不过第一次写的时候，代码规划的稀烂：

不过总归把表完整打出来了，而且和手算的结果一样，说明思路是没问题的，重点还是一个算新的数据要根据已经算出的数据，就会简化一部分运算。

不过实际应用可能更需要的是展示具体的选择和最终的结果，而且上面的写法也太丑陋了，因此优化一下：

其中找出所选的物品是根据结果和表格来逆向推导的，这次的代码已经简洁了不少。

不过，如果只是需要一个结果的话，观察到表格中的下面一行都是根据上面一行得到的，开一个大二维数组似乎有点奢侈，所以用滚动数组优化一下：

当然，也可以考虑在原始递归的思路上改进，这样的做优点是看起来比较简单，也很好写：

最后提醒一下数组记得初始化。