使用二分查找解决分数背包问题

Question

分数背包问题围绕着从给定的集合中选择物品以适合容量有限的背包。每个项目都有一个重量和与之相关的价值，目标是选择项目以在容量限制内最大化总价值。

在分数背包问题中，与0/1背包问题不同，我们可以获取物品的分数，使我们能够获得更好的整体价值。这使得分数背包问题对于现实场景更加灵活和实用。

分数背包问题可以使用二分查找来解决吗？

Answer 1

是的，您可以编写一个二分搜索解决方案。但这效率很低。

如果您选择这样做，搜索空间将是可能答案的范围。即 0 到 V。V 是所有项目值的总和。

您将使用

low

= 0,

hi

= V 开始二分查找。 要检查是否需要消除左半部分或右半部分，您必须计算

mid

是否可以作为您可能的答案。为了检查这一点，您将贪婪地选择每单位重量价值最高的物品。

所以你最终将不得不采取贪婪的路径，首先使二分搜索变得多余。