金银岛金属最优装载：部分背包问题详解与Python实现

## 🧠 问题分析 这是一个**部分背包问题**（Fractional Knapsack Problem），因为金属可以**任意分割**，且价值与重量成正比。 我们需要在总重量不超过 `w` 的前提下，最大化总价值。 **核心思路**： 计算每种金属的**单位价值**（价值/重量），优先选择单位价值最高的金属，直到背包装满。 --- ## 📦 算法步骤 1. 读取输入： - 承重上限 `w` - 金属种类数 `s` - 每种金属的总重量 `n_i` 和总价值 `v_i` 2. 计算每种金属的**单位价值** `unit_value = v_i / n_i` 3. 按单位价值**从高到低**排序 4. 遍历排序后的金属： - 如果当前金属可以全部装入（剩余容量 >= 金属重量），则全部装入，更新总价值和剩余容量 - 否则只装入剩余容量部分，按比例计算价值，然后结束循环 5. 输出总价值，**保留两位小数** --- ## 🧮 样例验证 样例输入： ``` 50 4 10 100 50 30 7 34 87 100 ``` 解析： - 金属1：重量10，价值100 → 单位价值 10.0 - 金属2：重量50，价值30 → 单位价值 0.6 - 金属3：重量7，价值34 → 单位价值 ≈ 4.857 - 金属4：重量87，价值100 → 单位价值 ≈ 1.149 按单位价值排序： 1. 金属1：单位价值 10.0，重量10 2. 金属3：单位价值 4.857，重量7 3. 金属4：单位价值 1.149，重量87 4. 金属2：单位价值 0.6，重量50 装入过程： - 装入金属1全部：重量10，价值100，剩余容量40 - 装入金属3全部：重量7，价值34，剩余容量33 - 金属4单位价值1.149，重量87 > 剩余33，只装33：价值 = 33 × (100/87) ≈ 37.931 总价值 = 100 + 34 + 37.931 ≈ 171.931 → 输出 171.93 ✅ --- ## 💻 代码实现（Python） ```python def fractional_knapsack(): w = int(input()) # 承重上限 s = int(input()) # 金属种类数 data = list(map(int, input().split())) metals = [] for i in range(0, 2 * s, 2): weight = data[i] value = data[i + 1] unit_value = value / weight metals.append((unit_value, weight, value)) # 按单位价值降序排序 metals.sort(key=lambda x: x[0], reverse=True) total_value = 0.0 remaining = w for unit_val, weight, value in metals: if remaining >= weight: # 全部装入 total_value += value remaining -= weight else: # 只装一部分 total_value += unit_val * remaining break print(f"{total_value:.2f}") if __name__ == "__main__": fractional_knapsack() ``` --- ## 🔍 关键点解释 - **单位价值计算**：`v_i / n_i`，使用浮点数确保精度。 - **排序**：Python 的 `sort(reverse=True)` 确保先装单位价值最高的。 - **比例计算**：当只能装一部分时，价值 = 剩余容量 × 单位价值。 - **输出格式**：`f"{total_value:.2f}"` 确保两位小数。 --- ## ⚠️ 注意事项 1. **浮点数精度**：计算单位价值时使用浮点数，但最终结果要求两位小数，一般精度足够。 2. **输入格式**：题目输入是两行金属数据，但样例中金属数据在一行，代码按一行读取处理。 3. **边界情况**： - 如果总重量小于 `w`，则全部装入。 - 如果 `w=0`（但题目 w>1），则输出 0.00。 4. **复杂度**：排序 O(s log s)，遍历 O(s)，效率很高。 --- ## 🚀 扩展与优化 - **大整数处理**：如果重量和价值很大，单位价值计算仍可用浮点数，但总价值可能需用高精度小数（Python 的 `decimal` 模块）。 - **多语言实现**：C++ 可用 `pair<double, pair<int, int>>` 存储并排序。 - **实际应用**：资源分配、货物装载等场景。 --- ## 📚 学习资源 - [部分背包问题 - Wikipedia](https://en.wikipedia.org/wiki/Continuous_knapsack_problem) - [Greedy Algorithms - GeeksforGeeks](https://www.geeksforgeeks.org/fractional-knapsack-problem/) --- ######[AI写代码神器 | 1149点数解答 | 2026-03-15 18:31:56]