TreeviewCopyright © aleen42 all right reserved, powered by aleen42

0-1 Knapsack Problem(0-1背包) Back

Overview

  • 每個item只能取值0或1, 求如何存放背包才能獲取利益最大值
  • : 用容量j去裝i個items, 最多能裝多少個
  • : 第i個item的重量
  • : 第i個item的價值

Optimal Substructure

  • 當我們求時, 若不取第i個item, 則必定等於;而若取, 則的值為加上該item的價值.

Recursive Expression

Solution

  • 最優解的值:
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.