分數揹包

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 = 18110/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 =回答