happy_arrange

概要

　幸せな配属問題を解くアルゴリズムの実装です。 ここでは幸せな配属問題を以下のように定義しています。

• n人がM個の部署に対してそれぞれ第H希望までの希望を出す。
• 第k希望の部署に配属された場合、その人の幸福度はp_kである。
• 希望の部署に配属されなかった場合、その人の幸福度は0である。
• 以上のような条件の下で、全員の幸福度の総和が出来る限り高くなるような配属方法を見つける。

詳細はここをご覧ください。

How to Compile

必要なもの

• g++
• boost

コマンド

単にmakeを実行すればO.K.です。

How to Use

通常は以下のように実行します。

./happy_arrange -c -i path/to/input.txt

-cオプションを付けると、探索時に枝刈りを行います。 入力ファイル名は-iオプションで指定して下さい。 入力ファイルは以下のような形式になります。

n
M
部署0の定員
部署1の定員
...
部署M-1の定員
0人目の第0希望 0人目の第1希望 ... 0人目の第H-1希望
1人目の第0希望 1人目の第1希望 ... 1人目の第H-1希望
...
n-1人目の第0希望 n-1人目の第1希望 ... n-1人目の第H-1希望

デフォルトでは第三希望まで選べますが、これを変更したい場合は 実行時に-sオプションを指定して下さい。

// 第五希望まで選択する場合
./happy_arrange -s 8:5:3:2:1 -i path/to/input.txt

このように、志望度が高い方の幸福度から順にコロン区切りで数値を並べて下さい。