TreeviewCopyright © aleen42 all right reserved, powered by aleen42

Fractional Knapsack Problem(分數) Back


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

Greedy Solution

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

As the plugin is integrated with a code management system like GitLab or GitHub, you may have to auth with your account before leaving comments around this article.

Notice: This plugin has used Cookie to store your token with an expiration.