我有一个大小为 [3][x] 的二维矩阵,其中填充了数字。我想根据条件从这个矩阵中选择 x 个数字
- 每一列中只有一个数字。
- 每行最多“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 作为最佳解决方案。
我正在尝试优化我的解决方案并寻找更好的算法。有人可以为我提供一些最佳解决方案的好主意吗?
最佳答案
这个问题让我想起了这个:http://projecteuler.net/problem=345
关于C++ 算法 : Pick n numbers from 2D Matrix based on certain conditions,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11659972/