0

次の場合に出力を返すために、O(n)またはO(n log n)でアプローチを見つけようとしています。n個の要素を持つセットがあり、指定された数に加算されるセット内の最小の数のセットを見つける必要がある場合。

たとえば、A = [0,9,1,2,5,4]、iがq = 6で与えられた場合、可能な組み合わせは(2 + 4)、(1 + 5)であり、次の場合はnullを返す必要があります。適切なサブセットが見つかりませんか?、これは宿題の質問ではありません。優れたプログラミングアプローチについて学びたいだけです。

4

1 に答える 1

1

一般的な問題はhttp://en.wikipedia.org/wiki/Subset_sum_problemです。

私たちの知る限りでは、この問題を解決する多項式速度のアルゴリズムはなく、存在しないと考えられています。ただし、いくつかの適切な近似方法が存在します。

于 2013-02-19T04:34:17.500 に答える