背包问题（动态规划）

背包问题是一种组合优化的问题，它有多种变体，但最常见的两种是0/1背包问题和完全背包问题。

0/1背包问题

问题描述： 假设你有一个背包，背包的容量为W（可以是重量或者体积等度量），同时有n个物品，每个物品都有自己的重量w[i]和价值v[i]。现在的目标是选择一些物品放入背包，使得背包中物品的总价值最大，但背包的总重量不能超过W。

特点：

• 每个物品只能选择一次，即不能分割。

• 选择放入背包或者不放入背包。

解决方案：

动态规划：这是解决0/1背包问题最常见的方法。通过构建一个二维数组dp，其中dp[i] [j]表示考虑前i个物品，背包容量为j时的最大价值。状态转移方程为： dp[i] [j]=max⁡(dp[i−1] [j],dp[i−1] [j−w[i]]+v[i]), dp[i] [j]=max(dp[i−1] [j],dp[i−1] [j−w[i]]+v[i]) 其中，如果选择第i个物品，则背包容量减去该物品的重量，总价值加上该物品的价值；如果不选择，则总价值不变。

已知w[]和v[]
int[][] dp = new int[n + 1][m + 1]for(int i = 1; i <= n; i++) {//遍历物品，注意下标的对应关系，这里都假设物品从下标1开始记录for(int j = 1; j <= m; j++) {//遍历容量if(j >= w[i])dp[i][j] = Math.max(d[i-1][j], dp[i-1][j-w[i]] + v[i]);	}
}

但是我们观察动态规划方程发现：对于考虑前i个物品的时候我们只需要用到i-1这一个状态，所以我们能不能将二维的数组压缩成一维的呢？答案显然是可以的

我们现在设dp[j]是容量j时的最大价值，因为我们外层循环的i一直在自增，所以对于上一次的dp[j]就相当与dp[i-1] [j], 所以我们只要不断更新dp[j]就行。那是否是在上述代码的基础上将递推方程由 dp[i] [j]=max⁡(dp[i−1] [j],dp[i−1] [j−w[i]]+v[i])改为dp[j] = max(dp[j], dp[j-w[i]] + v[i])就万事大吉了呢？宝贝你显然是太天真了

我们再来捋一下，如果我们用for(int j = 1; j <= m; j++)，我们每次更新都是从低位开始的，并且后续的递推要用到前面的结论，那我们来举例一下：

如果有3个物品他们的花费和价值是

W: 1 2 3

V: 2 1 3

对于容量为5的背包

i=1时

dp[1]=2, dp[2] = 4, dp[3] = 6, dp[4] = 8, dp[5] = 10 有没有发现端倪为毛我这次的修改全体现到之后的更新上了这不对吧，按我们的设想因该是i=2的那次才会应用上才对（但是这在完全背包问题中会被用到）

我们换倒序一下for(int j = m; j > 0; j--)

i=1时

dp[5] = 2, dp[4] = 2, dp[3] = 2, dp[2] = 2, dp[1] = 2;

i=2时

dp[5] = 3, dp[4] = 3, d[3] = 3, dp[2] = 2, dp[1] = 2

i=3时

dp[5] = 5, dp[4] = 5, d[3] = 3, dp[2] = 2, dp[1] = 2

这不就全对上了嘛，所以倒序可以避免这次的修改影响这次其它容量时的更新

代码如下：

已知w[]和v[]
int[] dp = new int[m + 1]for(int i = 1; i <= n; i++) {//遍历物品，注意下标的对应关系，这里都假设物品从下标1开始记录for(int j = m; j > 0; j--) {//遍历容量dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);	}
}

还有个无伤大雅的小优化，for(int j = m; j >= w[i]; j--), 因为你剩余的空间如果都放不下这个物体了，那这个物体的价值自然不会对答案产生影响，并且后续的遍历中也不存在能放得下这个物体的情况，可以直接跳过

已知w[]和v[]
int[] dp = new int[m + 1]for(int i = 1; i <= n; i++) {//遍历物品，注意下标的对应关系，这里都假设物品从下标1开始记录for(int j = m; j >= w[i]; j--) {//遍历容量dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);	}
}

完全背包问题

问题描述： 与0/1背包问题类似，但每个物品可以无限次选择。

特点：

• 每个物品可以被选择多次。

解决方案：

• 动态规划：同样使用动态规划，但是状态转移方程有所不同，因为物品可以被重复选择： dp[j]=max⁡(dp[j],dp[j−w[i]]+v[i]) , dp[j]=max⁡(dp[j],dp[j−w[i]]+v[i])其中，对于每个物品，我们尝试多次放入背包，直到背包容量不足以再放入该物品为止。

代码：

已知w[]和v[]
int[] dp = new int[m + 1]for(int i = 1; i <= n; i++) {//遍历物品，注意下标的对应关系，这里都假设物品从下标1开始记录for(int j = 1; j <= w; j++) {//遍历容量if(j >= w[i])dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);	}
}