本文共 1990 字，大约阅读时间需要 6 分钟。

序：

01背包问题是一类经典的动态规划问题，每一个物品可以选或者不选。通过动态规划，可以使得前i件物品的选择仅与前i-1件的物品选择有关，是不是有点像马尔可夫链？

题目概述：

有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何将物品放入背包，使得背包内物品的总价值最大。其中每件物品只有1件。

分析：

如果每件物品均判断在或不在，则会导致2^n的复杂度，这是令人崩溃的。因此我们另寻僻径。

令dp[i][v]表示前i件物品（1 <= i <= n, 0 <= v <= V)装入容量为v的背包中所能获得的最大价值，怎么求解dp[i][v]呢？有两种策略。

1：不放第i件物品，此时dp[i][v] = dp[i-1][v] 2：放第i件物品，此时dp[i][v] = dp[i-1][v-w[i]] + c[i],即通过牺牲空间换取价值。

因此，状态转移方程即为：

dp[i][v] = max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]) 其中（1 <= i <= n, w[i] <= v <= V) 边界为：dp[0][v] = 0 (0 <= v <= V) 最后，对dp[n][v] (0 <= v <= V)，也就说选到最后一个物品时，剩下的容量为v。由于剩下的容量由前n-1个物品的选择决定，所以需要对所有的dp[n][v]取最大值后方为结果。

举一个例子方便说明：

5 8 // n == 5, V == 83 5 1 2 2 // w[i]4 5 2 1 3 // c[i]

核心代码如下：

for(int i = 1; i <= n; i++){
       for(int v = w[i]; v <= V; v++)    {
           dp[i][v] = max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);    }}

我们来模拟一下：

i=1时：

v从3到8到中间取值, w[1] = 3, c[1] = 4 dp[1][3] = max(0, 3) = 4；同理，dp[1][k] = 4 (k从3到8中取值)

i=2时：

v从5到8中间取值，w[2] = 5, c[2] = 5 dp[2][5] = max(4,5) = 5 dp[2][6] = max(4,5) = 5 = dp[2][7] dp[2][8] = max(4, dp[1][3] + 5) = 9

i=3时：

v从1到8中间取值，w[3] = 1, c[3] = 2 dp[3][1] = … = dp[3][4] = 2 dp[3][5] = 5 dp[3][6] = max(dp[2][6], dp[2][5] + 2) = 7 dp[3][7] = max(dp[2][7], dp[2][6] + 2) = 7 = dp[3][8]

i=4时：

v从2到8中间取值，w[4] = 2, c[4] = 1 dp[4][2] = max(dp[3][2], dp[3][0] + 1) = 2 dp[4][3] = max(dp[3][3], dp[3][1] + 1) = 3 dp[4][4] = max(dp[3][4], dp[3][2] + 1) = 3 dp[4][5] = max(dp[3][5], dp[3][3] + 1) = 5 dp[4][6] = max(dp[3][6], dp[3][4] + 1) = 7 dp[4][7] = max(dp[3][7], dp[3][5] + 1) = 7 dp[4][8] = max(dp[3][8], dp[3][6] + 1) = 8

i=5时：

v从2到8中间取值，w[4] = 2, c[4] = 3 dp[5][2] = max(dp[4][2], dp[4][0] + 3) = 3 dp[5][3] = max(dp[4][3], dp[4][1] + 3) = 3 dp[5][4] = max(dp[4][4], dp[4][2] + 3) = 5 dp[5][5] = max(dp[4][5], dp[4][3] + 3) = 6 dp[5][6] = max(dp[4][6], dp[4][4] + 3) = 7 dp[5][7] = max(dp[4][7], dp[4][5] + 3) = 8 dp[5][8] = max(dp[4][8], dp[4][6] + 3) = 10

因此，按照这两重循环走一遍，最终答案为10。

总结：

书上是对最后一个循环取最大值，但我根据观察发现当容量最大时dp才是最大的。那么最大容量能不能直接输出dp[n][V]呢？欢迎大家一起探讨！

转载地址：https://bridge-killer.blog.csdn.net/article/details/115261267 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！