1

私は処理するのが難しいと思うかなり難しい仕事を持っています。

配列とその長さを指定すると、サブ配列のペアを出力する再帰関数 (ループはまったくありません) を作成しようとしています。それぞれの合計は、配列全体の合計の半分になります。つまり、配列は整数の 2 つのグループに分割され、それらの合計が等しくなります。

たとえば、配列 {1,2,2,0,5} が与えられた場合、関数は {1,2,2} {0,5} を出力する必要があります。

配列自体とそのサイズのみを取得する関数を使用して、再帰的に行う必要があります。また、問題を解決するために追加の再帰関数を 1 つだけ使用することも許可されています。

どんな考えやアイデアでも大歓迎です。

またあったね！このようなクラスのコードを取得しました

int SubsetSum(int arr[], int idx, int n, int S) {
if (S==0) return 1; //This is stopping condition #1.
if (S<0 || n==0) return 0; //This is stopping condition #2.
return SubsetSum(arr, idx+1, n-1, S-arr[idx]) || SubsetSum(arr, idx+1, n-1, S);
}

「 || 」演算子は、再帰に関して何を意味しますか? ありがとうございます！

4

2 に答える 2

1

最初に配列全体の合計を計算します (偶数の方がよいでしょう)。これにより、バイナリ ナップザックルーチンを使用して到達できる半分の合計が得られます。

Java のStack Overflow には再帰的な実装もあります。これは C とあまり変わらず、要件を満たします。

于 2012-12-17T21:34:27.637 に答える
0

要素が1つだけになるまで、配列とサブ配列を中央から分割します。

最初の要素を2番目の要素と比較し、これらの整数の合計を見つけます。

その後、これらの合計をバイナリ要素の比較に使用します。この比較を行うときは、合計を見つけます。たとえば、サブ配列は{1,2}と{0,3}です。最初の要素0と1を見てください。小さな要素が表示されたら、そのサブ配列（{0,3}）の他の要素を取得します。その後、合計は3になります。他の部分の合計は1で、他の要素（2）を取ります。現在、合計は両方で3です。そして、これをすべてのサブアレイに使用できます。

解決策がわかりません。しかし、それは分割統治アルゴリズムのように思えます。

于 2012-12-17T21:37:51.310 に答える