ナップサック

説明

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

品物は、品物の配列として表されます。 それぞれの品物には、重さと価値があります。 与えられる価値は、すべて正の値です。 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を超える価値にはできません。

トラック固有の注意点

Schemeのバージョンでは、引数はナップザックのcapacity、weightsのリスト、valuesのリストです。 入力の検証をする必要はありません。テストの入力には有効な値が使われていて、リストの長さも同じです。

---

出典

Wikipedia