subset-sum - 合計が特定のしきい値を超える最小の合計であるサブセット

Question

正の整数のコレクションが与えられた場合、合計がしきい値を超える最小の合計である整数のサブセットが必要です。

Answer 1

あなたの問題は部分和問題のバリエーションであり、 NP完全です。

理由を理解するために、問題を解決できるアルゴリズムがあり、それが合計sで答えを生成すると仮定しましょう。次に、s -1に等しい整数のサブセットが存在しないことを証明しました。つまり、サブセット和問題の解があります。

パフォーマンスが問題にならない場合は、考えられるすべてのセットを列挙することをお勧めします。パフォーマンスが問題になる場合は、動的計画法を使用するなど、この種のアルゴリズムを最適化する方法について、ウィキペディアのページを参照してみてください。そのページのアルゴリズムは、実際、サブセット和問題とほぼ同じくらい効率的に問題を解決するはずです。

Answer 2

「最小合計」: 古典的な「最大合計」問題があり、ここでよく説明されています: http://wordaligned.org/articles/the-maximum-subsequence-problem

これは、「しきい値を超える」条件の小さなバリエーションにすぎません。ループ内に余分な IF ステートメントがあるだけです。