3

O(3^n) だと思いますが、何かアイデアはありますか? このメソッドは、指定された数値が指定されたセットの任意のサブセットの合計であるかどうかを調べます (overroads boolean isSumOf(int[]s,int n))。このメソッドは、taget が 0 に等しい場合、またはセット内の現在の数値を消費する (または消費しない) 場合にすべての再帰呼び出しをチェックし、再試行しますが、target>0 であり、配列が使い果たされていない場合。

    * @param set a given set of natural numbers.
    * @param target the number. 
    * @param i where we are in the set.
    * @return true if we reached target, else returns false.
    **/
   private static boolean isSumOf(int[] set,int target,int i)
   {

        // Found the set if we are now at 0.
        boolean isSum = (target==0);
        // Look no further if no more to try.
        if ( target > 0 ) 
        {
            // Look no further if we've exhausted the array.
            if ( i < set.length )
            {
                // Try or consume this number in the set (or not) and try again.
                isSum = isSumOf(set, target - set[i], i)  // Consume the current number in the set and try again recursively. 
                    || isSumOf(set, target - set[i], i+1) // Consume the current number in the set and avdance to rhe next number.
                    || isSumOf(set, target, i+1); // Try the current number and avance to the next number in the set.
            }

        }

        return isSum;
4

3 に答える 3

3

あなたの問題はNP完全です。これらは悪いニュースです。

幸いなことに、これは非常によく知られている NP 完全問題です。ええ！

http://en.wikipedia.org/wiki/Subset_sum

コメントで述べたように、アルゴリズムは無期限に実行でき、中程度の入力サイズでも非常に長時間実行されます。

そのコードが適度なサイズの入力で実行されるという希望が少しでもある場合は、アプローチを再考する必要があります。

あなたのアプローチの大きな問題の 1 つは、多くの重複したサブ問題を計算していることです。通常の単純なフィボナッチ再帰実装を考えてみてください。

明るい面では、部分問題には非常に最適な構造があります。これは、問題が動的計画法アプローチの優れた候補になることを示す良い指標です。値を合計する正確な数値さえ必要とせず、ブール値の出力だけが必要であることが簡単になります。

私がリンクしたウィキペディアの記事では、いくつかの疑似多項式アプローチと、動的プログラミングによる多項式アプローチについて説明しています。

于 2012-12-28T12:56:28.383 に答える
1

O(3^n)最初の再帰呼び出しisSumOf(set, target - set[i], i)が先に進まずに自分自身を呼び出すため、より悪いように見えますi。大きなターゲットの場合、それぞれの分岐が膨大になりますi。

このような方法は、複雑さを軽減するためにメモ化の恩恵を受けることができます。

于 2012-12-28T12:58:24.657 に答える
1

set に 0 より大きい数値のみが含まれていると仮定します。またisSumOf(set, target - set[i], i+1)、結果を変更せずに 2 番目の再帰呼び出しを省略できることにも注意してください。これは、最初に set[i] を減算し (最初の再帰呼び出し)、次に i を進める (3 回目の再帰呼び出し) と同じです。この簡略化されたバージョンについて説明しています。

n がターゲットで k がセットのサイズの場合、複雑さは O(n^k) だと思いますが、完全な証明はありません。すべての可能性を列挙していて、パーティショニングが見つかったときに停止しないと仮定しましょう (実際のアルゴリズムは、ショートカットまたは || のために停止します)。最悪の場合は、セット内のすべての要素が 1 になるようです。したがって、再帰の最後に到達するには ik 回進める必要があり、i を進める各ステップの可能性は n 未満です。

于 2012-12-28T13:15:54.367 に答える