背包问题（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 \) 是背包的容量。
### 分数背包问题
分数背包问题（Fractional Knapsack Problem）是背包问题的一个变种，与 0/1 背包问题不同，
它允许分割物品，即可以选择物品的一部分以最大化总价值。这个问题通常可以通过贪心算
法来有效解决。
### 问题描述
分数背包问题可以描述如下：
- 有 \( n \) 个物品，每个物品 \( i \) 有一个价值 \( v_i \) 和一个重量 \( w_i \)。
- 一个背包的容量限制是 \( W \)。
- 目标是选择物品的一个最优组合，使得背包中的总价值最大，但总重量不超过 \( W \)。
### 解决方法：贪心算法
贪心算法解决分数背包问题的步骤如下：
1. **计算价值密度**：首先计算每个物品的价值密度（单位重量的价值），即 \( ext{value
