福利

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。她拿不到比 90 更高的价值，因为她的背包重量上限是 10。

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|

如果你愿意，可以覆盖用于输入的线性内存地址。