动态规划求解0/1背包问题

**动态规划求解0/1 背包问题**

**前言**

0/1 背包问题是一种经典的计算机科学问题，属于动态规划类别。该问题描述的是，在一堆物品中，每个物品都有一个重量和价值，我们需要选择一部分物品放入背包，使得背包的总重量不超过最大重量限制，同时尽可能地使得背包的总价值最大。

**动态规划求解0/1 背包问题**

### 动态规划思想动态规划是一种通过分解大问题为小子问题来解决问题的方法。对于0/1 背包问题，我们可以将其视为一个决策过程，每个决策都对应着选择或不选择某个物品。

### 状态转移方程我们定义状态变量 `dp[i][w]` 表示在前 `i` 个物品中，背包的最大重量为 `w` 时，背包的最大价值。那么，我们可以得到以下状态转移方程：

* 如果当前物品的重量大于 `w`，则不选择该物品，状态转移方程为：`dp[i][w] = dp[i-1][w]`
* 如果当前物品的重量小于或等于 `w`，则有两种选择：
* 不选择该物品，状态转移方程为：`dp[i][w] = dp[i-1][w]`
*选择该物品，状态转移方程为：`dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])`

### 状态转移矩阵我们可以将状态转移方程表示为一个状态转移矩阵：

| `i` | `0` | `1` | `2` | ... | `n` |
| --- | --- | --- | --- | ... | --- |
| `w=0` |0 |0 |0 | ... |0 |
| `w=1` |0 |0 |0 | ... |0 |
| `w=2` |0 |0 |0 | ... |0 |
| ... | ... | ... | ... | ... | ... |
| `w=n` |0 |0 |0 | ... |0 |

### 状态转移矩阵的填充我们可以通过递归地填充状态转移矩阵来求解背包问题。具体来说，我们需要填充以下部分：

* `dp[i][w] = dp[i-1][w]`（不选择当前物品）
* `dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])`（选择当前物品）

###代码示例

def knapsack(weights, values, capacity):
 n = len(values)
 dp = [[0 for _ in range(capacity +1)] for _ in range(n +1)]

 for i in range(1, n +1):
 for w in range(1, capacity +1):
 if weights[i -1] > w:
 dp[i][w] = dp[i -1][w]
 else:
 dp[i][w] = max(dp[i -1][w], dp[i -1][w - weights[i -1]] + values[i -1])

 return dp[n][capacity]

# 测试weights = [2,3,4,5]
values = [10,20,30,40]
capacity =7print(knapsack(weights, values, capacity)) # 输出:90