実数の mxn 行列があります。合計がしきい値より大きくなるように、各列から 1 つのエントリを選択するすべての方法を見つけるにはどうすればよいですか? 単純な方法は、すべての m^n の方法をチェックすることですが、複雑さをわずかに軽減する賢い方法はありますか? O(m^n) の境界を破ることはできないと思いますが、別のアルゴリズムで前の定数をわずかに減らすことができますか?
また、この問題が本質的によく知られている問題 (または類似の問題) である場合は、お知らせください。前もって感謝します。
いくつかの小さな改善:
しきい値が十分に高い場合、決して選択しないマトリックス エントリがいくつかあります。これは、他の列から他のエントリを選択しても、合計が十分に高くなることは不可能だからです。これらは前処理で取り除くことができます。
左から右にエントリを選択していると、残りの列からエントリを選択する方法に関係なく、終了するだけであることがわかります。
編集:選択した値の位置を取得したい!