title: Recursive solution of unbounded knapsack using logic of 0/1 knapsack
body: <p>Out of all the DP solutions I have checked out for 0/1 knapsack and unbounded knapsack, solution approaches are always defined like this :</p>
  
  <p><strong>0/1 knapsack</strong> : Maximise total value by either taking n-th item, or excluding n-th item. For example, <a href="https://www.geeksforgeeks.org/knapsack-problem/" rel="noreferrer">0/1 knapsack</a></p>
  
  <p><strong>unbounded knapsack</strong> : Maximise total value by considering n-th item as the last picked item, or (n-1) item as last picked one etc, etc. For example, <a href="https://www.geeksforgeeks.org/unbounded-knapsack-repetition-items-allowed/" rel="noreferrer">unbounded knapsack</a></p>
  
  <p>But unbounded knapsack can also be solved using logic of 0/1 knapsack with a minor tweak. What I mean is, that for 0/1 knapsack, we do the following (using the code from first link):</p>
  
  <pre><code>return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
              knapSack(W, wt, val, n-1)
            );
  </code></pre>
  
  <p>Notice how in the case when we are including <code>wt[n-1]</code> we are reducing the size of array by 1. This implies that <code>wt[n-1]</code> is now exhausted and hence, cannot be used again. But if in unbounded case, we don't reduce the array size by 1 (which would mean <code>wt[n-1]</code> can be used again), following slightly modified recurrence relation works fine:</p>
  
  <pre><code>return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n),
              knapSack(W, wt, val, n-1)
            );
  </code></pre>
  
  <p>Why is this approach for unbounded knapsack never mentioned anywhere then? Actually <a href="http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/DynProg/knapsack2.html" rel="noreferrer">here</a> it specifically says, we cannot use same logic as 0/1 knapsack for the unbounded one. Excerpt from that link :</p>
  
  <pre><code>Observation:
  I can never exhaust any item because there are an unbounded supply of items.
  Therefore:
  The technique used in the 0,1 knapsack problem cannot be used.
  </code></pre>
  
  <p>But I am not able to disprove that my above mentioned solution won't work. This idea came from <a href="https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/" rel="noreferrer">coin-change</a> problem, where you have to count number of ways to make change for a given amount, assuming infinite supply of coins.</p>
  
  <p>So my question is why the approach that I have proposed here, never used for unbounded knapsack or at least never mentioned anywhere? Can anyone please help me in proving or disproving this approach? Thanks in advance!</p>