背包問題

說明

你的任務是決定要挑選哪些物品，讓選中物品的總價值最大化，同時考量背包的負重上限。

物品會以陣列的形式表示。 每個物品都有重量和價值。 所有給定的值都是嚴格正數。 Bob 每種物品只能拿一個。

例如：

Items: [
  { "weight": 5, "value": 10 },
  { "weight": 4, "value": 40 },
  { "weight": 6, "value": 30 },
  { "weight": 4, "value": 50 }
]

Knapsack Maximum Weight: 10

以上面的例子來說，第一個物品的重量是 5、價值是 10，第二個物品的重量是 4、價值是 40，依此類推。 在這個例子中，Bob 應該拿第二個和第四個物品，才能讓價值最大化，也就是 90。 他的背包負重上限是 10，所以無法拿到超過 90 的價值。

---

出處

Wikipedia