分数背包问题和贪婪算法

可以取项目的分数, 而不必对每个项目进行二进制（0-1）选择。

分数背包问题可以通过贪婪策略解决, 而0-1问题则无法解决。

解决分数问题的步骤

1. 计算每件物品的每磅价值。
2. 遵循贪婪策略, 我们尽可能选择每磅最高价值的物品。
3. 如果该元素的供应已用完, 并且我们仍然可以运载更多, 我们将以每磅下一个值取尽可能多的元素。
4. 排序, 按每磅值排序的项目, 贪婪算法以O（n log n）时间运行。

Fractional Knapsack (Array v, Array w, int W)
1. for i= 1 to size (v)
2. do p [i] = v [i] / w [i]
3. Sort-Descending (p)
4. i ← 1
5. while (W>0)
6. do amount = min (W, w [i])
7. solution [i] = amount
8. W= W-amount
9. i ← i+1
10. return solution

示例：沿其各自的权重和值考虑5个项目：-

I =（I1, I2, I3, I4, I5）

w =（5、10、20、30、40）

v =（30, 20, 100, 90, 160）

背包容量W = 60

现在, 根据pi的减小值填充背包。

首先, 我们选择重量为5的物品Ii。

然后选择重量为20的物料I3。现在, 背包的总重量为20 + 5 = 25

现在下一项是I5, 其权重是40, 但是我们只需要35, 所以我们选择了它的小数部分,

解：

取每重量比的值, 即pi =

现在, 以降序排列pi的值。