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

首先需要生成所有子集

如果[A，B，C，d]給出陣列，考慮生成的子集從服用陣列的一個的每個元素在一個時間。

子集（X）包括Y = foreach x in X append y to x

隔空，我們得到的子集（A）= {[]，[A]}

飲用B，我們得到的子集（A，B）=子集（A）+（子集（a）中包括b）

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

採取C，子集（A，b，C）=子集（A，b）+（子集（A，b），包括C ）

= {[], [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; 
}