子集的這個解決方案如何總結問題的工作？

Question

這是子集求和問題的解決方案。它使用回溯。我一直在想這個問題超過2個小時，而我卻無法理解它。

編輯：我已經添加了一些基於我所瞭解的代碼的意見。如果我錯了，請糾正我。

#include <iostream> 

int n, d, w[10], x[10], count=0; 

void subset(int cs, int k, int r)//i dont understand the purpose of cs or of the array x[] 
{ 
    int i; 
    x[k] = 1; 

    if(cs + w[k] == d)  //if the first element is equivalent to the sum that is required 
    { 
     std::cout<< "\n\nSolution " << ++count << " is:"; 
     for(i=0; i<=k; i++) // so if the subset criteria are met then the array is printed. 
     if(x[i] == 1) 
      std::cout << w[i] << " "; 
    } 
    else if(cs + w[k] + w[k+1] <= d) //if the node is promising then go to the next node and    
     subset(cs + w[k], k+1, r - w[k]); //check if subset criteria are met 

    if(cs + w[k+1] <= d && cs + r - w[k] >= d) //else backtrack 
    { 
     x[k] = 0; 
     subset(cs, k+1, r-w[k]); 
    } 
} 

int main() 
{ 
    int sum=0, i; 

    std::cout << "enter n\n"; 
    std::cin >> n; 

    std::cout < <"enter " << n << " elements\n"; 
    for(i=0; i<n; i++) 
     std::cin >> w[i]; 

    for(i=0; i<n; i++) 
     sum += w[i]; 

    std::cout << "enter value of sum\n"; 
    std::cin >> d; 

    if(sum < d) 
     std::cout<<"INVALID SOLUTION\n"; 
    else 
     subset(0,0,sum); 

} 

注意：這是一個工作解決方案。它使用g ++編譯時工作。我很抱歉，如果這看起來太討厭，但我只是不太瞭解代碼，因此我不能給出太多的解釋。

Answer 1

cs是到目前爲止選擇的權重值的總和，而r是尚未被選擇的權重的總和值的餘數。 w [i]是權重i，當選擇權重[i]時，x [i]爲1。在所述子集的方法有兩個主要的決定分支：

重量選擇k：

// adding value of weight k to computed sum (cs) gives required sum, solution found 
if(cs+w[k]==d) 
{ 
cout<<"\n\nSolution "<<++count<<" is:"; 
for(i=0;i<=k;i++) 
    if(x[i]==1) 
    cout<<w[i]<<" "; 
} 

// both weight k and weight k+1 can be chosen without exceeding d, 
// so we choose k, and see if there's a solution for weight k+1 onwards 
// note that available weight values decreased from r to r-w[k] 
else if(cs+w[k]+w[k+1]<=d) 
    subset(cs+w[k],k+1,r-w[k]); 

權重k未選擇（注意的是，當溶液被發現被選擇權重k之後這甚至探索）：

// weight k+1 is choosable (does not exceed d), and despite not choosing weight k 
// there would be sufficient weights in r less w[k], and together with the chosen 
// pool cs to meet the requirement of d. 
if(cs+w[k+1]<=d && cs+r-w[k]>=d) 
{ 
x[k]=0; 
subset(cs,k+1,r-w[k]); 
} 

Answer 2

試試這個吧。

#include<iostream> 

int n,d,w[10],used[10],count=0; 
int cs = 0; // cs=Current Sum 

void subset(int k) 
{ 
    if (k >= n) return; // boundry check 
    int i; 
    used[k] = 1; // use element k 
    cs += w[k]; 

    if(cs == d) { 
     cout<<"\n\nSolution " << ++count << " is:"; 
     for(i=0;i <= k;i++) 
      if(used[i]==1) 
       cout<<w[i]<<" "; 
    } 
    if (cs < d) // only when current sum is not enough 
     subset(k + 1); 

    used[k] = 0; // not use element k 
    cs -= w[k]; 
    subset(k+1); 
} 

void main() 
{ 
    int sum=0,i; 

    cout<<"enter n\n"; 
    cin>>n; 

    cout<<"enter "<<n<<" elements\n"; 
    for(i=0;i<n;i++) 
    cin>>w[i]; 

    for(i=0;i<n;i++) 
    sum+=w[i]; 

    cout<<"enter value of sum\n"; 
    cin>>d; 
    cs = 0; 
    if(sum<d) 
     cout<<"INVALID SOLUTION\n"; 
    else 
     subset(0); 
} 

Answer 3

CS是當前總和並且x []是具有對屬於當前正在探索溶液分支那些元件1組的陣列。