分数背包

Question

我需要实现分数背包来解决这个问题

价值（$）20 50 10 90 110 70 60

重量（磅）3 4 1 5 6 3 4

但我对分数背包的工作方式感到困惑，我理解背包只能起作用。所以，在我的程序中输入例如重量限制= 7

它给了我143

你能帮我理解分数背包的工作原理吗？

谢谢

Answer 1

1. 按值/重量的降序创建排序列表。
2. 在你的情况下，列表将是20/3 = 6.6,50 / 4 = 12.75,10 / 1 = 10,90 / 5 = 18,110 / 6 = 18.3,70 / 3 = 23.3,60 / 4 = 15
3. 降序：23.3,18.3,18,15,12.5,10,6.6
4. 重量= 7。
5. 从Desc订单列表中选择项目1。其w = 3和3 <7所以总值= 0 + 70 = 70
6. 选择项目2，w = 6; 3 + 6 <7？没有（因此，它的一小部分）重量左= 7-3 = 4。取得的部分= 4 *（18.3）= 73.2总值= 70 + 73.2 = 143.2 =答案

Answer 2

第一步是要了解分数背包问题是一种贪婪的算法，因此满足了贪婪的选择属性。该属性指出第一选择将在所有最优解中，在这种情况下，将始终采用具有最大权重（k）/值（k）的项k并尽可能多地采用。在理解了这个概念后，我们可以继续使用该算法。

First Sort all the items in the backpack using weight(i)/value(i).
Then for each item in the sorted list from i=1 to n.

Take as much possible from item(i) until filled.

请注意，这不适用于0/1背包问题。