0/1ナップサック品目選択
各品目の整数重量と価値から、容量以内で価値の合計が最大になる選択を正確な動的計画法で探します。
例の値が入力されています。直接確認するか、値を変更してみてください。
入力はブラウザで処理されます。再読み込みすると例の値に戻ります。
使い方と例
DPᵢ(c)=max(DPᵢ₋₁(c),DPᵢ₋₁(c−wᵢ)+vᵢ); xᵢ∈{0,1}
重量・価値2,3 / 3,4 / 4,5、容量5では行1,2を選び、重量5・価値7です。
最大100品目、整数重量1〜10,000・価値0〜1,000,000・容量0〜10,000です。繰り返し選択と品目の分割は認めません。 浮動小数点の結果は最大有効数字12桁で表示します。
よくある質問
同じ品目を複数選択するには?
用意された個数だけ別の行に入力してください。各行は1回だけ選択でき、結果は行番号で表示します。
ナップサックの容量を使い切る必要がありますか?
いいえ。容量以下で価値の合計を最大化します。容量が余っていても最適な場合があります。
計算基準と参考資料
- Google OR-Tools: knapsack
容量制約内での分割できない品目の選択。