1

数値で満たされたサイズ [3][x] の 2D 行列があります。条件に基づいて、このマトリックスからx個の数字を選びたい

  1. 各列から正確に 1 つの数字。
  2. 各行から最大 'm' 個の数字 (3 行すべての合計は x の数字であり、3m > x である必要があります)

これらの選択された x 数の最小の合計を見つけたいです。

マトリックスから上記の条件に基づいて「x」の小さな数字を見つける反復アプローチに基づいて数字を選択することができました。しかし、私の答えは最適ではありません。例えば：

5 9 . . . . 
6 15 . . . .
7 19 . . . .

最初に 5 を選択したとします (したがって、6 と 7 は選択できません)。後で 9 を選択しようとしますが、row(0) の m 個の要素が終わった場合、15 を選択する必要があります。ここで、解は 5+15 = 20 になりますが、最適解として 6+9 = 15 を使用することもできました。

ソリューションを最適化し、より良いアルゴリズムを探しています。誰かが最適な解決策の良いアイデアを教えてくれますか?

4

1 に答える 1

0

この問題は私にこれを思い出させます: http://projecteuler.net/problem=345

ハンガリー語のアルゴリズムが機能する可能性があります: http://en.wikipedia.org/wiki/Hungarian_algorithm

于 2012-07-25T23:46:42.350 に答える