DAY45：动态规划（五）背包问题：01背包理论基础+二维DP解决01背包问题

**DAY45：动态规划（五）背包问题**

在前面的几篇文章中，我们已经学习了动态规划的基本概念、算法设计思想以及如何应用到实际的问题上。今天我们要讨论的是一个经典的问题——01背包问题。

**01背包问题**

01背包问题是这样定义的：假设有 n 个物品，每个物品都有一个重量和价值，且每个物品只能选择一次。如果总重量不超过 W，则求出能获得的最大价值。

例如，如果我们有以下物品：

| 物品 | 重量 |价值 |
| --- | --- | --- |
| A |2 |6 |
| B |3 |10 |
| C |1 |4 |

如果总重量不超过5，则求出能获得的最大价值。

**01背包问题的解决方案**

我们可以使用动态规划来解决这个问题。首先，我们需要定义一个二维数组 dp，用于存储每个物品的最大价值。

def knapsack(W, wt, val, n):
 # Create a table to store results of subproblems K = [[0 for w in range(W +1)] for i in range(n +1)]

 # Build the table. W is capacity, wt[i] is weight of the ith item,
 # val[i] is value of the ith item, and n is number of items.
 for i in range(n +1):
 for w in range(W +1):
 if i ==0 or w ==0:
 K[i][w] =0 elif wt[i -1] <= w:
 K[i][w] = max(val[i -1] + K[i -1][w - wt[i -1]], K[i -1][w])
 else:
 K[i][w] = K[i -1][w]

 return K[n][W]

在这个解决方案中，我们首先创建一个二维数组 dp，大小为 (n +1) x (W +1)，用于存储每个物品的最大价值。

然后，我们使用两个循环来填充这个数组。第一个循环是对物品的循环，第二个循环是对重量的循环。

在每次循环中，我们检查当前物品是否可以放入背包。如果可以，则我们计算当前物品的最大价值，并将其与不选择当前物品时的最大价值进行比较。然后，我们选择哪一个更大作为当前物品的最大价值。

如果当前物品不能放入背包，则我们直接使用不选择当前物品时的最大价值。

最后，我们返回二维数组 dp 中的最后一个元素，这就是能获得的最大价值。

**示例代码**

# Example usage:
W =5wt = [2,3,1]
val = [6,10,4]
n = len(val)

max_value = knapsack(W, wt, val, n)
print("Maximum value:", max_value)

在这个示例代码中，我们定义了一个背包的容量 W，三个物品的重量和价值，以及物品的数量 n。然后，我们调用函数 knapsack 来计算能获得的最大价值，并打印出结果。

**总结**

01背包问题是动态规划的一个经典问题。通过使用二维DP来解决这个问题，我们可以有效地求出能获得的最大价值。在本文中，我们提供了一个解决方案，包括示例代码和注释，以帮助读者理解背包问题及其解决方案。