特典

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

割引を受け取る

トラック

Haskell

演習

ナップサック

中級

はじめに

ボブは泥棒です。何か月もかけて入念に計画を練ったすえ、ついに高級店のセキュリティシステムを突破することに成功します。

目の前には、それぞれに価値と重さを持った品物がたくさん並んでいます。ボブはすべての品物を持ち帰りたいところですが、ナップザックに入る重さには限りがあります。ボブは、選んだ品物の価値の合計が最大になるように、どの品物を持っていくかを慎重に考えなければなりません。

説明

課題は、ナップサックの容量を考慮しながら、ボブが選んだ品物の合計の価値が最大になるように、どの品物を持っていくかを決めることです。

品物は、品物の配列として表されます。それぞれの品物には、重さと価値があります。与えられる価値はすべて、正の値です。ボブはそれぞれの品物を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、というようになっています。この例では、ボブは価値を最大にするために、2つ目と4つ目の品物を取るのがよいでしょう。この場合の価値は90になります。ナップサックの重さの上限は10なので、ボブが得られる価値は90を超えることはありません。