背包问题（Knapsack Problem）的贪心算法近似解 问题描述 背包问题是一个经典的组合优化问题：给定一组物品，每个物品有重量（weight）和价值（value），以及一个容量有限（capacity）的背包，如何选择物品装入背包，使得总价值最大？贪心算法无法保证获得最优解，但能快速给出近似解，适用于对精度要求不高的大规模问题。 贪心策略设计 贪心算法的核心是每一步选择当前最优的物品。常见的贪心策略包括： 价值密度优先 ：按单位重量价值（value/weight）降序排序，优先选择价值密度高的物品。 价值优先 ：直接按价值降序排序。 重量优先 ：按重量升序排序，优先选择轻的物品。 实践中， 价值密度优先 通常效果最好。以下以该策略为例分步讲解。 步骤分解 计算价值密度 对每个物品计算其价值密度： \[ \text{density}_ i = \frac{\text{value}_ i}{\text{weight}_ i} \] 例如，物品1：重量=2，价值=10 → 密度=5.0；物品2：重量=3，价值=12 → 密度=4.0。 按密度降序排序 将物品按价值密度从高到低排序。若密度相同，可任意排列（如按重量升序辅助排序）。 贪心选择物品 从密度最高的物品开始，依次尝试装入背包： 若当前物品重量 ≤ 剩余容量，则装入该物品，更新剩余容量和总价值。 若当前物品重量 > 剩余容量，则跳过该物品。 重复直到遍历完所有物品或背包已满。 算法终止 输出装入物品的总价值作为近似解。 示例演示 假设背包容量=5，物品如下： 物品A：重量=2，价值=6 → 密度=3.0 物品B：重量=3，价值=10 → 密度≈3.33 物品C：重量=1，价值=3 → 密度=3.0 按密度排序：B(3.33) → A(3.0) → C(3.0) 装入B：剩余容量=5-3=2，总价值=10 装入A：重量2 ≤ 剩余容量2，装入后剩余容量=0，总价值=16 背包已满，跳过C 最终解：总价值=16（此例中为最优解，但贪心法不一定总是最优）。 局限性分析 贪心法的缺陷在于无法处理“部分物品组合优于单个高密度物品”的情况。例如： 容量=10，物品1：重量=6，价值=60（密度=10）；物品2：重量=5，价值=50（密度=10）；物品3：重量=5，价值=50（密度=10） 贪心法可能先选物品1（价值60），但最优解是物品2+物品3（价值100）。 因此，贪心法适用于允许近似解的场景，若需精确解需用动态规划。 实际应用 贪心法因时间复杂度低（O(n log n)，主要来自排序）被广泛用于资源调度、缓存淘汰等实时性要求高的场景。