3

n 個のリストがある場合、各リストから番号を選択する必要があります。選択した番号を再度選択することはできません。選択した n 個の番号の最大合計を取得するにはどうすればよいですか? 例えば

list1:  4 5 7.
list2:  3 5 7.
list3:  1 5

リスト 1 から 7 を選択すると、リスト 2 で選択できる最大数は 5 です (同じ数を 2 回選択することはできないため)。リスト 2 から 5 を選択すると、リスト 3 から 1 しか選択できないため、合計は7+5+1=13

それは最良の選択ではありません。ただし、list1 から 4、list2 から 7、list3 から 5 を選択すると、合計は次のようになります。4+7+5=16

最大の合計を得るために選択を行うための最良の方法を見つけるアルゴリズムはありますか? ソリューションは完璧でなければなりません。

4

2 に答える 2

4

直接的なアルゴリズムはありませんが、ハンガリアン アルゴリズムを修正することで、問題を多項式時間で解くことができます。ウィキ

非負の n×n 行列が与えられます。ここで、i 番目の行と j 番目の列の要素は、j 番目のジョブを i 番目のワーカーに割り当てるコストを表します。コストが最小になる作業員へのジョブの割り当てを見つけなければなりません。目標が最大コストを生み出す割り当てを見つけることである場合、各コストを最大コストからコストを引いたものに置き換えることで、設定に合うように問題を変更できます。

次元 (K*K) の行列を作成します。ここで、K=max(n,リスト内の要素の最大数) です。

例えば：

List 1=1 2 3 4
List 2=5
List 3=9 10

The K*K matrix is:
1 2  3 4
5 0  0 0
9 10 0 0
0 0  0 0

次のアルゴリズムhttp://en.wikipedia.org/wiki/Hungarian_algorithm#Settingを上記のマトリックスに適用します。

于 2013-03-22T06:19:56.323 に答える