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

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

重量と容量を整数で指定し、0/1ナップサック問題で合計価値が最大となる組合せを1つ求めます。

1行に名前,重量,価値を半角カンマで区切って入力します。名前は前後の空白を除いた後で空でなく一意で、カンマを含めないでください。各欄の前後の空白は許容され、空白行は無視されます。価値の小数点にはピリオドを使います。

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

下の3行を貼り付け、別の容量欄に5を指定して計算します。最大価値は16、選択はA, Bです。コピーは結果をコピーし、クリアは容量も空にします。

物品は1〜200件、容量は1〜5000の整数、重量は1〜容量の整数、価値は0〜1000000000の空でない有限数で、小数も使えます。容量を超える物品があると入力全体がエラーになります。文字列上限はUTF-16コード単位500000個です。各物品は最大1回選択されます。表示は最大価値と名前のみで、合計重量は表示されません。同値の場合は後の物品を選ばないため、入力順で最適な選択が変わる場合があります。最小重量の優先はありません。価値が全て0なら0と空の選択です。小数演算には丸めがあり、正確な金額は整数単位に換算してください。