問題
$ m $ 人の応募者と $n$ 個の商品があり、応募者 $i$ の商品 $j$ に対する希望度 $A _ {ij} \geq 0$ が定まっている。商品 $j$ は $L _ j > 0$ 個しかなく、$1$ 人の応募者に $2$ 個以上の商品が当選することはないとする。 また、希望度が $0$ の商品に当選することはないとする。つまり、$X _ {ij} = 1, 0$ で応募者 $i$ が商品 $j$ に当選したかしなかったかを表すとすると、$X _ {ij}$ は $$\sum _ {j = 1} ^ {n} X _ {ij} \leq 1$$ $$ \sum _ {i = 1} ^ {m} X _ {ij} \leq L _ {ij}$$ $$A _ {ij} = 0 \Rightarrow X _ {ij} = 0$$ をみたす。 このとき、当選者の希望度の合計 $ \displaystyle \sum _ {i = 1} ^ {m} \sum _ {j = 1} ^ {n} A _ {ij} X _ {ij} $ を最大化するように、各商品の当選者を決定せよ。
解説
この問題をグラフ理論で表現する。応募者を表す点 $i = 1, \ldots, m $ と商品を表す点 $j = 1', \ldots, n'$ を用意し、$A _ {ij} > 0$ なら $i$ と $j$ を重み $A _ {ij}$ の辺で結び、重み付き二部グラフを作る。このグラフに対して、各 $i$ の次数が $1$ 以下で、各 $j$ の次数が $L _ {j}$ 以下になるような部分グラフで、重みの合計が最大になるようなものを見つければよい。
$m = n$ かつ $L _ {j} = 1$ のときは「重みつき最大二部マッチング問題」になり、以下の記事で解説されているように重みを負のコストと見做すことで最小費用流問題に帰着する。
これを拡張することで、今回の問題も最小費用流に帰着させることができる。具体的には、新たな点 $S$, $T$ を用意し、次のようなネットワークを構成する。
| 辺 | 費用 | 容量 |
|---|---|---|
| $S \rightarrow i$ | $0$ | $1$ |
| $i \rightarrow j$ | $- A _ {ij}$ | $1$ |
| $j \rightarrow T$ | $0$ | $L _ {j}$ |
このネットワークで、流量 $\displaystyle \sum _ {j = 1} ^ {n} L _ {j}$ の最小費用流を求めればよいが、解が存在しない場合もあるので、解が存在するまで流量を $1$ ずつ減らしていく必要がある。
最小費用流問題の解き方は以下などを参照されたい。
