{a1、a2、...、an}などの正の整数の配列があり、次の条件を満たす配列のすべての可能なサブセットを見つけたい:
(sum >= K)
ここで、K は正の整数です。この問題の解決策が動的プログラミングであることは知っていますが、この場合の使用方法を考えることができません。助けてください。
PS：すべてのサブセットが正確に必要なわけではありませんが、形成されたすべてのサブセットのすべての要素の積と言えます。
2740 次
1 に答える
0
あなたの問題は、0-1 ナップザック問題に似ていますが、例外は - 通常、この制限は、合計が Kよりも小さくなければならないということです。
しかし、制限がある場合、その合計がより大きくなければならないという問題をリストします。
したがって、たとえば、サブセットを見つけた場合、その合計が K より大きい場合、サブセットに含まれていないセットの任意の要素を追加できますが、これは依然として答えです。セットが{a1、a2、a3、a4} ans sum {a1} >= Kであると仮定しましょう。次に、a2、a3、およびa4をサブセットに追加する2 ^ 3の方法があります。
したがって、考えられるすべてのバリエーションをリストする必要があるため、この問題は指数関数の問題のように見えます。
最悪のケースは、K = 0 の場合です。0 より大きい N 個の要素があるため、2 ^ N 個のサブセットをリストする必要があります。
おそらく、このリンクはhttp://en.wikipedia.org/wiki/Subset_sum_problemに役立つ可能性があります
于 2013-08-08T12:12:15.840 に答える