Databases
StackOverflow2013
Postsdbo
POHow does this solution of the subset sum problem‍​​ work?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow does this solution of the subset sum problem‍​​ work?
    primarykey
    data
    text
    <p>this is a solution for the subset sum problem. It uses backtracking. I have been thinking about it for more than 2 hours now and i just cannot understand it. </p> <p>edit:I have added some comments to the code based on what i have understood. Please correct me if i am wrong.</p> <pre><code>#include &lt;iostream&gt; 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&lt;&lt; "\n\nSolution " &lt;&lt; ++count &lt;&lt; " is:"; for(i=0; i&lt;=k; i++) // so if the subset criteria are met then the array is printed. if(x[i] == 1) std::cout &lt;&lt; w[i] &lt;&lt; " "; } else if(cs + w[k] + w[k+1] &lt;= 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] &lt;= d &amp;&amp; cs + r - w[k] &gt;= d) //else backtrack { x[k] = 0; subset(cs, k+1, r-w[k]); } } int main() { int sum=0, i; std::cout &lt;&lt; "enter n\n"; std::cin &gt;&gt; n; std::cout &lt; &lt;"enter " &lt;&lt; n &lt;&lt; " elements\n"; for(i=0; i&lt;n; i++) std::cin &gt;&gt; w[i]; for(i=0; i&lt;n; i++) sum += w[i]; std::cout &lt;&lt; "enter value of sum\n"; std::cin &gt;&gt; d; if(sum &lt; d) std::cout&lt;&lt;"INVALID SOLUTION\n"; else subset(0,0,sum); } </code></pre> <p>Note: This is a working solution. It works when compiled with g++. I am sorry if this seems too obnoxious but i just did not understand much from the code and hence i cannot give much of an explanation.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USNullUserException
    1. USChaitanya Nettem
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow does this solution of the subset sum problem‍​​ work?
      1. This table or related slice is empty.
      1. VTApproveEditSuggestion
    2. VO
      singulars
      1. POHow does this solution of the subset sum problem‍​​ work?
      1. USNullUserException
      1. VTFavorite
    3. VO
      singulars
      1. POHow does this solution of the subset sum problem‍​​ work?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhy don't you add some comments to the code you posted with your thoughts on the parts you do understand and some highlights of those you don't?
      singulars
      1. POHow does this solution of the subset sum problem‍​​ work?
      1. USJohn Zwinck
    2. COIf you are completely stumped, go through some simple examples step-by-step with a debugger. Inspect the variables to see what's going on.
      singulars
      1. POHow does this solution of the subset sum problem‍​​ work?
      1. USreima
    3. CO@JohnZwinck I have added the comments. please correct them if i am wrong.
      singulars
      1. POHow does this solution of the subset sum problem‍​​ work?
      1. USChaitanya Nettem
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload