How do i solve these variations of the 0-1 knapsack algorithm?
<p>The knapsack can carry a maximum weight , say max_wt ; has n items with a given weight<code>wt[]</code> and a value<code>val[]</code>.I have two questions ( both seperate from each other ) :<br></p>

<ul>
<li>What is the maximum value we can carry if there was a second limit to the volume we could carry , vol[ ] ?</li>
<li>What are the  number of ways to carry a total of exactly z(&lt; n) items such that their sum of values is divisible by a number , say 8 ?</li>
</ul>

<p><strong>My Attempt</strong><br></p>

<ul>
<li><p>For the first question i refered <a href="https://stackoverflow.com/questions/1827600/multiple-constraint-knapsack-problem">this</a> stackoverflow post , but the only answer i could understand was one where the two constraints were merged ,but the run time complexity of that would be quite big i guess...what i was thinking was making a <code>dp[i][j][k]</code> , where i is the number of items selected , j is the max-wt selected at that point , k is the max-vol selected at that point and then my core of the code looked like <br>
<code>for(i=0 ; i &lt; n ; i++) \\ n is no. of items
for(j=0 ; j &lt; n ; j++) 
   for(k=0 ; k &lt; n ; k++)
   dp[i][j][k] = max( dp[i-1][j][k] , val[i] + dp[i-1][j-wt[j]][k-vol[k]]) ;</code><br>
, this seems alright , but gives me wrong answer ... i cant guess why :(</p></li>
<li><p>I can't start to think of the second problem, my friend did it by taking three states dp[i][j][k] where i and j are just same as first question(the usual ones) while 'k' keeps track of the total items selected , this idea isnt getting in my head . Plus , what will a state store , it usually stores max value possible till given state in classical knapsack problems , here i guess a state will store total combinations divisible by 8 till that state , but i cant convert this into code .</p></li>
</ul>

<p>p.s please try providing a solution with bottom up approach to the second question , i am very new to dynamic programming . ;)</p>