0-1ナップサック・予算内の案選択
バグ・不具合を報告
予算内で採用可否が二択の案件・施策を選び、価値の合計を最大化する。
各案の価値は同じ尺度の点数で比較してください。必須案だけで予算を超える場合は実行可能な組合せがありません。
金額・点数は整数のみ。入力を四捨五入せず、価値が同点なら使用コストが少ない組合せを選びます。
項目を入力・選択してから「計算する」を押してください。
必要な入力・選択は2項目です。
計算結果
—点
- 使用コスト
- —円
- 残予算
- —円
- 採用件数
- —件
値を入力して計算してください。
この計算機は使いやすかったですか?
回答はサイト改善のために保存します。入力値・計算結果は送りません。
ありがとうございます。よかったら、上の共有ボタンからこの計算機を紹介しませんか?
計算方法・適用範囲・出典
計算方法
採用をx_i∈{0,1}として、Σ(価値_i×x_i)を最大化。Σ(コスト_i×x_i)≦予算、必ず採用はx_i=1、採用しない案はx_i=0。自由な案は各1回だけ採否を選びます。コスト順に非劣な状態を残す動的計画法で、価値が同じなら低コストを優先します。実行可能な組合せは必須採用の合計が予算以内なら存在します。近似解は出しません。
最適価値、使用コスト、残予算、採用件数、案別の採否一覧。
計算例(架空の数値)
架空の3案:A(4円・6点)、B(3円・5点)、C(2円・3点)、予算5円ならBとCを採用し、価値8点・使用5円・残0円です。
適用対象と限界
互いに独立した案を各1回まで選べ、コストを円・価値を同一尺度の点数として入力できる組合せ。数量を連続的に分ける配分、依存関係・排他組・複数予算・時系列・価値の確率推定は扱いません。計算量上限を超える問題は近似せず計算を中止します。。
採用した方式
- 0-1ナップサック・厳密DP(Sparse Pareto frontier 0-1 DP v1.0):対象範囲 コスト・価値は非負整数、単一予算、案ごとの採否固定のみ/適用地域 JP(一般算術)
方法と出典
方法:Sparse Pareto frontier 0-1 DP v1.0(2026-11-13)。データ記録日:2026-11-13。