49

私はこの問題に取り組んでいます:

X = {x1, x2 ,…, xn}部分和問題は、一連のn整数と別の整数を入力として受け取りますK。問題は、要素の合計が になるサブセットX'が存在するかどうかを確認し、存在する場合はそのサブセットを見つけることです。たとえば、サブセットの合計が であるため、答えはです。実行時間が少なくとも である Subset Sum のアルゴリズムを実装します。XKX = {5, 3, 11, 8, 2}K = 16YESX' = {5, 11}16O(nK)

複雑さに注意してくださいO(nK)。動的計画法が役立つと思います。

指数時間アルゴリズムを見つけましたが、役に立ちません。

誰かがこの問題を解決するのを手伝ってくれますか?

4

12 に答える 12

20

すべての数値が正のように見えるため、動的計画法を使用してこれを解決できます。

possibleStart は、最初の値が true、残りが false のサイズ K+1のブール配列になります。i 番目の値は、i のサブセットの合計を達成できるかどうかを表します。セット内の各数値 n について、possible配列をループし、i 番目の値が true の場合は、i+n 番目の値も true に設定します。

最後に、 の k 番目の値possibleが true の場合、k のサブセット和を形成できます。問題は O(NK) 時間で解決されました。

ウィキペディアのサブセット和問題に関するページには、正であることが保証されていない整数のセットに適用されるこのアルゴリズムの詳細な説明があります。

于 2010-12-04T21:43:42.287 に答える
9

Wikiのアルゴリズムを読むことをお勧めします。アルゴリズムはそこに存在します. 解については疑似多項式時間動的計画法解を参照してくださいO(P*n). 解は多項式時間ではありません. (p,n) では多項式ですが, n+log P (入力のサイズ) では多項式ではありませんP. 2^n のように非常に大きい場合、解 P*n = (2^n)*n は一般に多項式時間解ではありませんが、p が n の多項式関数によって制限されている場合、多項式時間アルゴリズムになります。

この問題は NPC ですが、そのためのPseudo polynomial timeアルゴリズムがあり、問題に属しweakly NP-Completeます。また、問題もありStrongly NP-Completeます。つまり、P=NP でないとアルゴリズムを見つけることができずpseudo polynomial time、この問題はこの範囲の問題ではありません。 、 だからなんとなく簡単です。

私はこれをできるだけ簡単に言いましたが、それは強い NP 完全または弱い NP 完全の問題の正確な定義ではありません。

詳細については、Garey and Johnsonの第 4 章を参照してください。

于 2010-12-05T16:03:18.240 に答える
5

私はパーティーに遅れたようです。これが私の 2 セントです。最初の項目 ( のインデックス)を使用すると、セットから合計を取得できるboolean[] solution[n+1][k+1]ような をsolution[i][j]作成します。そうでなければ。最後に戻ります：truei0i-1jfalsesolution[k][n]

次の点を推測できます。

  1. sum がゼロの場合、任意の数の要素に対して常に可能な答え (空のセット) になります。だからすべて真実です。
  2. セットが空の場合、サブセットを持つことはできないため、K を取得する方法はありません。したがって、可能な答えはありません。すべて偽。
  3. 部分集合 X1 (X の最後の要素を含まない X の部分集合) が k の部分集合和を持つ場合、X にもそれが X1 として含まれます。たとえば、X1={1,3,5} および k=8 の場合、X1 に部分和がある場合、X={1,3,5,7} にも部分和があります
  4. i/p セット X = {1,3,5,7,19} および k=20 の場合、X が 20 のサブセット和の可能性を知りたい場合、x1={1,3,5,7} 20-19、つまり 1 の部分集合和を持つことができます。これは、k >= 19、つまり X の最後の要素の場合にのみ適用されます。

上記のポイントに基づいて、アルゴリズムを次のように簡単に記述できます。

public class SubSetSum {
    boolean[][] solution; 
    int[] input;
    int k;

    public SubSetSum(int[] input, int targetSum) {
        this.input = input;
        this.k = targetSum;
        this.solution = new boolean[input.length+1][k+1];
    }

    public boolean subsetSum() {
        int n = input.length;

        for (int i = 0; i <= n; i++) {     //case 1
            solution[i][0] = true;
        }

        for (int j = 0; j <= k; j++) {    // case 2
            solution[0][j] = false;
        }

        for (int i = 1; i <= n; i++) {                  // n times
            for (int j = 1; j <= k; j++) {              // k times and time complexity O(n*k)
                if(solution[i-1][j]) {
                    solution[i][j] = solution[i-1][j];      // case 3
                    continue;
                }
                if(j >= input[i-1])  {                       // case 4
                    solution[i][j] = solution[i-1][j-input[i-1]];
                }
            }
        }
        return solution[n][k];
    }
}
于 2018-10-14T08:29:50.993 に答える
4

一般に、O(2^(n/2)) 未満で実行されるサブセット合計の既知のアルゴリズムはありません。

于 2010-12-04T21:36:48.457 に答える
4 
void subsetSum (int arr[], int size, int target) {
  int i, j ;
  int **table ;
  table = (int **) malloc (sizeof(int*) * (size+1)) ;
  for ( i = 0 ; i <= size ; i ++ ) {
    table[i] = (int *) malloc (sizeof(int) * (target+1)) ;
    table[i][0] = 1 ;
  }
  for ( j = 1 ; j <= target ; j ++ )
    table[0][j] = 0 ;
  for ( i = 1 ; i <= size ; i ++ ) {
    for ( j = 1 ; j <= target ; j ++ )
      table[i][j] = table[i-1][j] || (arr[i-1] <= j && table[i-1][j-arr[i-1]] ) ;
  } 
  if ( table[size][target] == 1 )
    printf ( "\ntarget sum found\n" ) ; 
  else printf ( "\nTarget sum do not found!\n" ) ;
  free (table) ;
}
于 2012-09-24T18:23:59.080 に答える
1

M をすべての要素の合計とします。K<=M であることに注意してください

let m be a Boolean array [0...M]
set all elements of m to be False
m[0]=1
for all numbers in the set let a[i] be the ith number
    for j = M to a[i]
        m[j] = m[j] | m[j-a[i]];

次に、単に m[k] をテストします

于 2015-04-03T17:26:27.063 に答える
1 
function subsetsum(a, n) {
    var r = [];
    for (var i = parseInt(a.map(function() { return 1 }).join(''), 2); i; i--) {
        var b = i.toString(2).split('').reverse().map(function(v, i) {
            return Number(v) * a[i]
        }).filter(Boolean);
        if (eval(b.join('+')) == n) r.push(b);
    }
    return r;
}

var a = [5, 3, 11, 8, 2];
var n = 16;
console.log(subsetsum(a, n)); // -> [[3, 11, 2], [5, 3, 8], [5, 11]]

力ずくで -- 並べ替えを忘れて、すべての組み合わせを試すと、eval パーサーが Array.reduce に勝ります (負の数でも機能します)。

于 2019-04-26T05:23:44.477 に答える
0

1次元配列を使用したDPソリューション（ここではDP配列の処理順序が重要です）。

bool subsetsum_dp(vector<int>& v, int sum)
{
    int n = v.size();
    const int MAX_ELEMENT = 100;
    const int MAX_ELEMENT_VALUE = 1000;
    static int dp[MAX_ELEMENT*MAX_ELEMENT_VALUE + 1]; memset(dp, 0, sizeof(dp));

    dp[0] = 1;

    for (int i = 0; i < n; i++)
    {
        for (int j = MAX_ELEMENT*MAX_ELEMENT_VALUE; j >= 0; j--)
        {
            if (j - v[i] < 0) continue;
            if (dp[j - v[i]]) dp[j] = 1; 
        }
    }

    return dp[sum] ? true : false;
}
于 2014-12-06T18:36:37.627 に答える