背包DP

问题引入

假设有一个容量为10的背包，而物品的价值和体积如下表所示，我们的目标是在容量不超过背包的前提下拿走尽可能多的价值的物品

序号	1	2	3	4	5
体积	3	4	6	2	3
价值	4	3	7	6	2

对于这种问题我们发现对于一个物品只有拿和不拿两种情况，因此我们可以通过这个来枚举。

所有情况是种复杂度为，但是这对于我们来说要枚举太多，效率过低。那么我们就需要去探寻每一种之间的关系。

假设代表可拿走物品为1~i的情况下，容量为j的背包能够拿走的最大价值。 那么对于有以下的递推关系式 其中是第个物品的体积，是第个物品的价值

那么如何获得和？看到这个递归式第一反应就是递归，但是很明显它的复杂度是和没优化一摸一样！

时间复杂度优化

但是如果以一棵树来看，它访问了许多重复的路径，进行了许多重复的计算，因此看上去复杂度高。那么我们首要解决的问题就是如何减少重复的计算。我们将得到和的方式改为计算到。而到可以由到得到，因此对于我们的计算时间复杂度便降低到

空间复杂度优化

明显对于任意一个到只会用一次，那么我们将原来的二维数组变为的一维数组。但是要注意更新的时候哟要从开始到，因为大背包空间在放入一个物品后，会有多余的空间去放其他物品，这时需要本轮未更新时的。