0-1ナップサック・予算内の案選択

予算内で採用可否が二択の案件・施策を選び、価値の合計を最大化する。

各案の価値は同じ尺度の点数で比較してください。必須案だけで予算を超える場合は実行可能な組合せがありません。

金額・点数は整数のみ。入力を四捨五入せず、価値が同点なら使用コストが少ない組合せを選びます。

項目を入力・選択してから「計算する」を押してください。

必要な入力・選択は2項目です。

0~1,000,000,000,000円の整数。消費税等を含めた同じ基準のコストを入力してください。

比較する案必須
行案名コスト(円)価値(点)採否制約 任意操作
1
2

4列を左端の欄へタブ区切りで貼り付けられます。36行まで。

入力済みの行だけを対象とします。空欄を残した行は計算できません。制約が空欄なら自由選択です。


計算結果

値を入力して計算してください。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

採用を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。