SubsetSum Печать списка

Question

Проблема заключается в печати всех подмножеств, которые суммируются до значения. Я написал код, чтобы проверить, есть ли возможное подмножество. Может ли кто-нибудь дать идею напечатать числа, которые составляют сумму. Ниже мой код. Предположим, что для простоты массив содержит только + ve nos.

void subsetsum(int A[], int target) { 

int N = sizeof(A)/sizeof(int), sum = 0; 

for(int i = 0; i < N; i++) sum += A[i]; 

vector<bool> V(sum + 1, 0); 
V[0] = 1; 
for(int i = 0; i < N; i++) 
    for(int j = sum; j >= 0; j--) { 
     if(j + A[i] <= sum && V[j]) V[A[i] + j] = 1; 
    } 
    if(V[target]) cout << "Sumbset sum exists" << endl; 
    else cout << "Sumbset sum doesnt exist" << endl; 
} 

Answer 1

Прежде всего, необходимо создать все подмножества

Если [а, Ь, с, d] дается массив, подумайте о создании подмножеств, принимая каждый элемент из массива по одному.

подмножество (X) в том числе у = foreach x in X append y to x

Взятия, мы получаем подмножество (а) = {[], [а]}

Take Ь, мы получаем подмножество (а, Ь) = подмножеств (а) + (подмножеств (а) в том числе и б)

= { [], [a] } + { [b], [a,b] } = { [], [a], [b], [a,b] }

Примите с, подмножеств (а, б, в) = подмножества (A, B) + (подмножества (A, B), в том числе гр)

= {[], [a],[b],[a,b]} + {[c], [a,c], [b,c], [a,b,c]}

Как только вы получите все подмножества, напечатайте те, чьи суммы равны цели. Вы можете изменить вышеуказанный алгоритм, если вам не нужны подмножества.

Answer 2

Вот ответ на JavaScript:

function subsetsum(A, target) { 

//int N = sizeof(A)/sizeof(int), sum = 0; 
var N = A.length, sum = 0; 

//for(int i = 0; i < N; i++) sum += A[i]; 
for(var i = 0; i < N; i++) sum += A[i]; 

// vector<bool> V(sum + 1, 0); 
var V = []; 

V[0] = []; 
for(var i = 0; i < N; i++) { 
    for(var j = sum; j >= 0; j--) { 
     if(j + A[i] <= sum && V[j]) { 
      //Join the subset of the memoized result to this result. 
      V[A[i] + j] = [A[i]].concat(V[j]); 
     } 
    } 
} 
console.log(V); 
//evaluates to true if V[target] exists 
return !!V[target]; 
} 

Answer 3

функции, чтобы найти мощность набор функции vector<int>

vector<vector<int>> power_set(const vector<int>& nums) { 
    if (nums.empty()) { return { {} }; } 
    auto set = power_set(vector<int>(begin(nums) +1, end(nums))); 
    auto tmp = set; 
    for (auto& p : tmp) { 
    p.push_back(nums[0]); 
    } 
    set.insert(end(set), begin(tmp), end(tmp)); 
    return set; 
} 

, что вернуть все наборы в силе установить эту сумму целевых

vector<vector<int>> test_sum(const vector<vector<int>>& ps, int target) { 
    vector<vector<int>> v; 
    for (auto& p : ps) { 
    int sum = accumulate(begin(p), end(p), 0); 
    if (sum == target) { 
     v.push_back(p); 
    } 
    } 
    return v; 
} 

Answer 4

Я изменил ваш код, чтобы напечатать цифры.

void subsetsum(int A[], int target) { 

    int N = sizeof(A)/sizeof(int), sum = 0; 

    for (int i = 0; i < N; i++) sum += A[i]; 

    vector<bool> V(sum + 1, 0); 
    V[0] = 1; 
    for (int i = 0; i < N; i++) 
     for (int j = sum; j >= 0; j--) { 
      if (j + A[i] <= sum && V[j]) V[A[i] + j] = 1; 
     } 
    if (V[target]) cout << "Sumbset sum exists" << endl; 
    else cout << "Sumbset sum doesnt exist" << endl; 

    if (V[target]) 
    { 
     for (int i = N - 1; i >= 0; i--) 
     { 
      if (V[target - A[i]] == 1) printf("%d, ", A[i]), target -= A[i]; 
     } 
     printf("\n"); 
    } 
} 

или Вот мой вариант с вектором

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; 
     } 
    } 
    if (dp[sum]) 
    { 
     for (int i = n - 1; i >= 0; i--) 
     { 
      if (dp[sum - v[i]] == 1) printf("%d, ", v[i]), sum -= v[i]; 
     } 
     printf("\n"); 
    } 

    return dp[sum] ? true : false; 
}