私はこの問題に取り組んでいます:
X = {x1, x2 ,…, xn}部分和問題は、一連のn整数と別の整数を入力として受け取りますK。問題は、要素の合計が になるサブセットX'が存在するかどうかを確認し、存在する場合はそのサブセットを見つけることです。たとえば、サブセットの合計が であるため、答えはです。実行時間が少なくとも である Subset Sum のアルゴリズムを実装します。XKX = {5, 3, 11, 8, 2}K = 16YESX' = {5, 11}16O(nK)
複雑さに注意してくださいO(nK)。動的計画法が役立つと思います。
指数時間アルゴリズムを見つけましたが、役に立ちません。
誰かがこの問題を解決するのを手伝ってくれますか?
すべての数値が正のように見えるため、動的計画法を使用してこれを解決できます。
possibleStart は、最初の値が true、残りが false のサイズ K+1のブール配列になります。i 番目の値は、i のサブセットの合計を達成できるかどうかを表します。セット内の各数値 n について、possible配列をループし、i 番目の値が true の場合は、i+n 番目の値も true に設定します。
最後に、 の k 番目の値possibleが true の場合、k のサブセット和を形成できます。問題は O(NK) 時間で解決されました。
ウィキペディアのサブセット和問題に関するページには、正であることが保証されていない整数のセットに適用されるこのアルゴリズムの詳細な説明があります。
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 章を参照してください。
私はパーティーに遅れたようです。これが私の 2 セントです。最初の項目 ( のインデックス)を使用すると、セットから合計を取得できるboolean[] solution[n+1][k+1]ような をsolution[i][j]作成します。そうでなければ。最後に戻ります：truei0i-1jfalsesolution[k][n]
次の点を推測できます。
上記のポイントに基づいて、アルゴリズムを次のように簡単に記述できます。
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];
}
}
一般に、O(2^(n/2)) 未満で実行されるサブセット合計の既知のアルゴリズムはありません。
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) ;
}
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] をテストします
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 に勝ります (負の数でも機能します)。
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;
}