優惠

Ready to put your newfound language skills into use? Get 40% off CodeCrafter's real-world proficiency projects!

領取你的折扣

學習軌道

WebAssembly

練習

背包問題

困難

簡介

Lhakpa 是一位雪巴人登山嚮導兼挑夫。經過數個月的仔細規劃後，Lhakpa 任職的探險隊即將出發。她會依自己搬運到基地營的物品價值獲得報酬。

她面前擺著許多物品，每一件都有自己的價值與重量。 Lhakpa 很想把所有物品都帶走，但她的背包能承載的重量有限。

說明

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

物品會以陣列的形式表示。每個物品都有重量和價值。所有給定的價值一律為正數。 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 的價值。

WebAssembly 專屬說明

項目會透過線性記憶體傳遞，第一個項目位於位移 0 的位置。每個項目都以一對 32 位元整數表示。這一對數字中，第一個是重量，第二個是價值。

舉例來說，假設有一個包含兩個項目的陣列，第一個是weight=1, value=2，第二個是weight=5, value=8。因此，這個陣列在記憶體中會長這樣：

| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
| - item 1 weight - | -- item 1 value - | - item 2 weight - | -- item 2 value - |
|0x01,0x00,0x00,0x00|0x02,0x00,0x00,0x00|0x05,0x00,0x00,0x00|0x08,0x00,0x00,0x00|

如果你想要的話，可以覆寫用於輸入的線性記憶體位址。