能否使用Binary Search求解Fractional Knapsack问题？

分数背包问题概述 #

• 分数背包问题核心：从给定物品集合中挑选物品放入容量有限的背包，每个物品对应固定重量与价值，目标是在不超过背包容量的前提下，最大化装入物品的总价值。
• 与0/1背包问题的关键区别：分数背包允许选取物品的一部分，而非只能选择完整物品，这一特性让它在现实场景中具备更强的灵活性与实用性。

能否用二分查找求解？ #

答案是可以，不过常规贪心算法在效率上更优，二分查找是一种可行的替代思路，具体实现逻辑如下：

核心思路 #

通过二分查找可能的最大单位价值阈值，验证是否存在一种物品选取方案，使得总价值不低于该阈值对应预期值，同时总重量不超过背包容量。

具体步骤 #

1. 确定二分范围：

   • 左边界left设为0（最低可能的单位价值）；
   • 右边界right设为所有物品中最高的单位价值（或直接取总价值与最小重量的比值，确保覆盖所有可能的单位价值上限）。

2. 阈值验证逻辑：
   对于二分过程中的中间值mid（当前假设的单位价值阈值），计算所有物品在满足“单位价值≥mid”条件下的最大可贡献重量：

   • 若物品i的单位价值v_i/w_i ≥ mid：直接选取整个物品，贡献重量w_i；
   • 若物品i的单位价值v_i/w_i < mid：最多选取x = v_i/mid重量的该物品（此时这部分物品的总价值刚好等于v_i，且单位价值达标）。
     将所有物品的贡献重量求和，若总和≤背包容量C，说明可以达到至少mid*C的总价值，此时尝试提高阈值（调整left = mid）；否则降低阈值（调整right = mid）。

3. 终止条件：
   当二分的精度达到题目要求（比如保留指定小数位数）时，停止迭代，最终的left（或right）乘以背包容量C，即为最大化的总价值。

对比贪心算法 #

常规贪心算法的时间复杂度为O(n log n)（主要来自按单位价值排序），而二分查找的时间复杂度为O(n * log(max_value/epsilon))（epsilon为精度要求）。在大多数场景下，贪心算法更高效，二分查找更多作为一种思路补充，适用于某些特定的问题变形场景。

内容的提问来源于stack exchange，提问作者ShouryaSetu