オンラインナップサック問題ソルバー

0/1ナップサック問題とは

容量が限られたバッグに、各品物を最大1個まで入れるとき、価値の合計が最大になる組み合わせを求める問題です。このツールは動的計画法を用いて厳密な最適解を計算します。

入力形式と制約

各品物は「名前,整数の重さ,数値の価値」の形式で1行に1つずつ入力します。名前は空でなく、重さは正の整数で容量以下、価値は0から1000000000の整数です。品物は1個から200個まで指定できます。

計算例

例えば、以下の3品物を考えます。

A,2,6
B,3,10
C,4,12

容量を5とすると、最大価値は16で、選択される品物はAとBです。

出力と注意点

出力には最大価値と、その価値を達成する1つの最適な組み合わせが表示されます。同点の組み合わせが複数ある場合でも、すべてを列挙するわけではなく、重さが軽いなどの副次的な基準で最適化することもありません。また、このツールは分数や複数個の選択、多次元、通貨換算には対応していません。価値は抽象的なスコアとして扱ってください。

よくある質問

品物の数に制限はありますか？

1個から200個まで入力できます。

重さや価値に小数は使えますか？

いいえ、重さは整数、価値は整数で指定してください。

同点の組み合わせが複数ある場合、どれが選ばれますか？

このツールは特定の1つの最適解を返しますが、どの組み合わせが選ばれるかは保証されません。

チェックリスト

• 各品物を1行に「名前,重さ,価値」の形式で入力しましたか？
• 容量は1から5000の整数ですか？
• 品物の名前は一意で空ではありませんか？
• 重さは容量以下ですか？