異なる指標の合計を最大化する

Question

n x pのAの行列をn > pとし、各要素を0 <= A <= 1とします。私はAにpの要素を見つけたいと思います。合計の合計が最大になり、各要素が異なる行になるようにします。したがって、考えられるべき異なる組み合わせがn permute pある。この問題の名前はありますか？私はナップザック問題などのものを見つけましたが、設定が異なります。さらに、彼らはn=300, p=10のためにこれを計算するための効率的なアルゴリズムですか？たとえば、各列の最大値が異なる行にあるような場合など、いくつかの特別なケースをチェックする必要があります。それ以外の場合は、私は動的なプログラミングに任されていますか？ありがとう！

Answer 1

maximum matching in a weighted bipartite graph（assignment problemとも呼ばれます）。列と行はグラフパーツ（エージェントとタスク）、セルはエッジ（タスク割り当て）です。

これは、多項式であるHungarian algorithmによって効果的に解決されます。