分数背包问题和贪婪算法 _贪婪算法

可以取项目的分数, 而不必对每个项目进行二进制（0-1）选择。
分数背包问题可以通过贪婪策略解决, 而0-1问题则无法解决。
解决分数问题的步骤

计算每件物品的每磅价值。
遵循贪婪策略, 我们尽可能选择每磅最高价值的物品。
如果该元素的供应已用完, 并且我们仍然可以运载更多, 我们将以每磅下一个值取尽可能多的元素。
排序, 按每磅值排序的项目, 贪婪算法以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 ← 15. while (W> 0)6. do amount = min (W, w [i])7. solution [i] = amount8. W= W-amount9. i ← i+110. 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, 所以我们选择了它的小数部分,