可以取项目的分数, 而不必对每个项目进行二进制(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 ← 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, 所以我们选择了它的小数部分,
解:
项目 | 无线 | 我们 |
---|---|---|
I1 | 5 | 30 |
I2 | 10 | 20 |
I3 | 20 | 100 |
I4 | 30 | 90 |
I5 | 40 | 160 |
取每重量比的值, 即pi =
项目 | 无线 | 我们 | Pi= |
---|---|---|---|
I1 | 5 | 30 | 6.0 |
I2 | 10 | 20 | 2.0 |
I3 | 20 | 100 | 5.0 |
I4 | 30 | 90 | 3.0 |
I5 | 40 | 160 | 4.0 |
现在, 以降序排列pi的值。
项目 | 无线 | 我们 | pi= |
---|---|---|---|
I1 | 5 | 30 | 6.0 |
I3 | 20 | 100 | 5.0 |
I5 | 40 | 160 | 4.0 |
I4 | 30 | 90 | 3.0 |
I2 | 10 | 20 | 2.0 |