Project Selection Problem
N個のプロジェクトがある
プロジェクトiをやると収入r_iが得られる
M個の機械がある
機械jを買うとコストc_jが掛かる
プロジェクトをやるためにはそのプロジェクトに必要な機械を買わなければならない
利益=収入-コストを最大化するにはどのプロジェクトを選べば良いか？
頂点の塗り分けと解釈すると理解しやすい
スタートと同じ色で塗られたプロジェクトが「選択したプロジェクト」
同じ色で塗られたマシンが「購入されたマシン」
図中の-pはrと読み替える
----
下記の解説は最小カットのカットは「辺を切る」ではないを理解する前に書いたのであまり良くない説明
N個のプロジェクトがある
M個の機械がある
プロジェクトはいくつかの機械を必要とする
プロジェクトpiを選ぶと収入r(pi)が得られる
必要な機械qjを買うとコストc(qj)が掛かる
利益-コストを最大化するにはどのプロジェクトを選べば良いか？
「あるプロジェクトが選ばれたなら、必要な機械を買わなければならない」と言う制約を無限大の辺で表現する
右側か左側かどちらかを切らなければならない
プロジェクトの辺を切らないことを「プロジェクトの選択」と見る
機械の辺を切ることを「機械の購入」と見る
プロジェクトを選択した(辺を切らない)なら、機械を購入する(辺を切る)必要がある
プロジェクトを選択しない=収入減、機械を買う=コスト、この和を最小化したい→最小カット
二択の選択肢から選ぶ問題とも解釈できる
Related Pages
- →✅ARC074D×kupc2016e×✅ABC193F×✅arc085e×arc031d×arc107f×wupc2019f×💻kupc2017h×ttpc2015l×二部グラフの片側を反転×最小カットのカットは「辺を切る」ではない×最小カットを使って「燃やす埋める問題」を解く→
- →dp×重み付き区間スケジューリング問題×連立1次方程式×最小カット×最大独立集合問題×二部グラフの最大マッチング×dilworthの定理×区間スケジューリング×貪欲法×区間スケジューリング問題×マトロイド×マトロイド交差×有向全域木×カラフル全域木×指数時間アルゴリズム入門→
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×unionfind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
- →アルゴリズム×蟻本×区間スケジューリング×二分探索木×unionfind×最短路問題×最小全域木×ユークリッドの互除法×ニ分探索×しゃくとり法×半分全列挙×座標圧縮×セグメント木×binary_lndexed_tree×バケット法×平方分割×ビットdp×bitdp×行列累乗×繰り返し二乗法×最大流×最小カット×二部マッチング×一般マッチング×マッチング×辺カバー×安定集合×点カバー×最小費用流×凸包×grundy数×強連結成分分解×2-sat×lca×ダブリング×接尾辞配列×sparse_table×rmq×atcoder→
- →atcoder×atcoder_library_practice_contest×numba×cython×フェニック木×セグメント木×遅延伝搬セグメント木×接尾辞配列×lcp_array×pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ×中国剰余定理×floor_sum×np.convolve×two_snuke×長整数が速い×dsu×unionfind×最大流×最小費用流×scc×2-sat→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]