我有一个实数的 mxn 矩阵。如何找到从每一列中选择一个条目以使它们的总和大于某个阈值的所有方法？天真的方法是检查所有 m^n 方法，但是有什么聪明的方法可以稍微降低复杂性吗？我猜你不能打破 O(m^n) 的界限，但也许另一种算法可以稍微减少前面的常数？
另外，如果这个问题本质上是一个众所周知的问题（或类似问题），请告诉我。先感谢您。
一些小的改进：
如果阈值足够高，那么您将永远不会选择一些矩阵条目，因为无论您从其他列中选择什么其他条目，总和都不可能足够高。我们可以在预处理中消除这些。
当您从左到右选择条目时，您会发现无论您如何从其余列中选择条目，都只需退出。
编辑：我想获得所选值的位置！
Is the postion of the values selected on the matrix a concern, or you just want to know the values selected on each column for each path?
If it is option two then ordering the values in each column would allow you to truncate search as soon as a value on a column no longer satisfies it. e.g.:
8 7 4 9 2
5 6 4 8 2
3 3 2 3 1
2 2 2 1 1
suppose your threshold is 25, then as you pick 8, 7, 4, 3, 2 you can stop your search on the 4th and 5th column for values 8,7,4 of column 1, 2 and 3. And so on...
Here's an algorithm based on your improvements that runs only a constant factor longer than is necessary to write out all of the output.
Before beginning, sort within each column from greatest to least and compute suffix sums of the first row (i.e., scan right to left to determine, for each j, the max contribution of columns j..n).
Now do a recursive search with your pruning rule: for the current column, try the values from greatest to least and recurse, breaking out of the row loop if the maximum contribution of the remaining columns plus the sum so far is less than the threshold.
For the analysis, look at the recursion tree. Each leaf is a solution, which, being of size n, pays for every ancestor. There is constant overhead at each node.
If somehow you can consume each solution in sublinear time, perhaps by intertwining producer and consumer, there's another optimization that drops the computation to O(1) per instead of O(n) by detecting when it's necessary to take all of the maximums remaining. This is accomplished by sorting the columns by the gap between the greatest and second-greatest element; then, as soon as there is only one choice for a column going left to right, the others are forced too.