背包问题（Knapsack Problem）是组合优化中的一个经典问题，属于计算复杂性理论中的 NP
完全问题。它描述了这样一个场景：给定一组项目，每个项目都有其自身的价值和重量，确
定在不超过给定总重量限制的情况下，如何选择项目，使得它们的总价值最大。
背包问题可以具体分为两种类型：
1. **0/1 背包问题**：每个项目只能选取一次，即要么完全包含在背包中，要么完全不包含。
2. **分数背包问题**（也称为贪心背包问题）：可以选取项目的任意部分，即可以分割项目。
### 0/1 背包问题
在 0/1 背包问题中，目标是最大化背包中物品的总价值，同时确保总重量不超过背包的容量
限制。这个问题可以用动态规划（Dynamic Programming, DP）来解决。
**动态规划解法**：
1. 定义状态：\( dp[i][j] \) 表示在考虑前 \( i \) 个物品，且背包容量为 \( j \) 时能获得的最
大价值。
2. 状态转移方程：对于每个物品 \( i \) 和每个容量 \( j \)，有两种选择，要么不选择物品
\( i \)（此时 \( dp[i][j] = dp[i-1][j] \)），要么选择物品 \( i \)（此时 \( dp[i][j] = dp[i-1][j-w[i]] +
v[i] \)，其中 \( w[i] \) 和 \( v[i] \) 分别是物品 \( i \) 的重量和价值）。
3. 初始化：\( dp[0][j] = 0 \)，表示没有物品时，无论背包容量多大，价值都是 0。
4. 最终结果：\( dp[n][C] \)，其中 \( n \) 是物品的总数，\( C \) 是背包的容量。
0/1 背包问题是一种典型的组合优化问题，其名称来源于每个物品只能被选择一次，即要么
完全包含在背包中，要么完全不包含。这个问题在运筹学、管理科学以及计算机科学中都有
广泛的应用。
### 问题描述
假设有 \( n \) 个物品和一个容量为 \( W \) 的背包。每个物品 \( i \) 都有一个重量 \( w_i \)
和一个价值 \( v_i \)。目标是选择一组物品，使得这些物品的总价值最大，同时保证总重量
不超过背包的容量。
### 解决方法：动态规划
动态规划是解决 0/1 背包问题的一种有效方法。以下是使用动态规划解决该问题的基本步骤：
1. **定义状态**：使用 \( dp[i][j] \) 表示在考虑前 \( i \) 个物品时，背包容量为 \( j \) 能够
获得的最大价值。
2. **状态转移方程**：对于每个物品 \( i \) 和每个背包容量 \( j \)，有两种选择：
- 不选择物品 \( i \)，此时 \( dp[i][j] = dp[i-1][j] \)。
