Fractional Knapsack Problem(分數) Back

Overview

  • 0-1 Knapsack不同的是, 分數背包可以分割地取一個物品, 而非要不取, 要不不取.

Greedy Solution

  • 每次選擇value/weight最大的物品放入包裏直到無法完全放入, 最後分割物品填滿包則會得到最優解
  • 上面情況的最優解: 取item1 10, item2 20 和 item3 20則會得到最大價值240.

results matching ""

    No results matching ""