1:1の最小費用割当
担当者と作業の正方形費用表から、重複のない全体割当と最小費用を計算します。
例の値が入力されています。直接確認するか、値を変更してみてください。
入力はブラウザで処理されます。再読み込みすると例の値に戻ります。
使い方と例
DP(mask∪{j})=min(DP(mask)+cost[popcount(mask),j])
既定の最適割当は1→2、2→1、3→3で、合計2+6+1=9です。
1〜10行の正方行列、費用0〜1,000,000の整数です。全行・全列を正確に割り当て、禁止組合せ・容量・先行関係は扱いません。 浮動小数点の結果は最大有効数字12桁で表示します。
よくある質問
割当費用0は禁止を意味しますか?
いいえ。0は費用のない許可された割当です。禁止する組合せはこのモデルの範囲外です。
担当者数と作業数が違う場合は?
長方形の入力は拒否します。空き枠の意味と費用を決めたうえで、明示的なダミー行・列を追加できます。
計算基準と参考資料
- Google OR-Tools: assignment
費用行列による完全な1:1割当モデル。