背包問題

說明

你的任務是決定該帶走哪些物品，並把背包的負重上限納入考量，讓挑選出的物品總價值最大化。

物品會以陣列的形式表示。 每個物品都有重量和價值。 所有給定的價值一律為正數。 Lhakpa 每種物品只能帶走一個。

例如：

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，其餘依此類推。 在這個例子裡，Lhakpa 應該帶走第二個和第四個物品，才能讓她的總價值最大化；以這個例子來說，最大值是 90。 因為背包的重量上限是 10，她沒辦法取得超過 90 的價值。

---

出處

Wikipedia