ナップサック

説明

ここでの課題は、ナップサックに入る重さの上限を踏まえて、持ち出す品物を選び、選んだ品物の合計価値が最大になるようにすることです。

品物は、品物の配列として表されます。 それぞれの品物には、重さと価値があります。 与えられる価値は、すべて正の値です。 Lhakpaは、同じ品物を1つしか持ち出すことはできません。

たとえば、次のとおりです。

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

Knapsack Maximum Weight: 10

上の例では、1つ目の品物の重さは5、価値は10、2つ目の品物の重さは4、価値は40、というようになっています。 この例では、Lhakpaは2つ目と4つ目の品物を持ち出すと価値が最大になり、その価値は90です。 ナップサックの重さの上限は10なので、90を超える価値にはできません。

WebAssembly 固有の注意点

アイテムはリニアメモリを介して渡され、最初のアイテムはオフセット0に置かれます。 各アイテムは、32ビット整数のペアとして表されます。 ペアの最初の数値が重さで、2番目の数値が価値です。

たとえば、2つのアイテムからなるリストを考えてみましょう。1つ目がweight=1, value=2で、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|

必要であれば、入力に使われたリニアメモリのアドレスを上書きしてもかまいません。

---

出典

Wikipedia