Databases
StackOverflow2013
Postsdbo
POKnapsack code - not working for some cases
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POKnapsack code - not working for some cases
    text
    copied!<p>My code is as the following:</p> <pre><code> #include&lt;stdio.h&gt; int max(int a,int b) { return a&gt;b?a:b; } int Knapsack(int items,int weight[],int value[],int maxWeight) { int dp[items+1][maxWeight+1]; /* dp[i][w] represents maximum value that can be attained if the maximum weight is w and items are chosen from 1...i */ /* dp[0][w] = 0 for all w because we have chosen 0 items */ int iter,w; for(iter=0;iter&lt;=maxWeight;iter++) { dp[0][iter]=0; } /* dp[i][0] = 0 for all w because maximum weight we can take is 0 */ for(iter=0;iter&lt;=items;iter++) { dp[iter][0]=0; } for(iter=1;iter&lt;=items;iter++) { for(w=0;w&lt;=maxWeight;w=w+1) { dp[iter][w] = dp[iter-1][w]; /* If I do not take this item */ if(w-weight[iter] &gt;=0) { /* suppose if I take this item */ dp[iter][w] = max( (dp[iter][w]) , (dp[iter-1][w-weight[iter]])+value[iter]); } } } return dp[items][maxWeight]; } int main() { int items=9; int weight[/*items+1*/10]={60, 10, 20, 20, 20, 20, 10, 10, 10}; int value[/*items+1*/10]={73, 81, 86, 72, 90, 77, 85, 70, 87}; int iter; int i; int maxWeight=180; for (i=0;i&lt;10;i++){ value[i] = value[i]*weight[i]; } printf("Max value attained can be %d\n",Knapsack(items,weight,value,maxWeight)); } </code></pre> <p>My knapsack code is working when </p> <pre><code>items=12; int weight[/*items+1*/13]={60, 20, 20, 20, 10, 20, 10, 10, 10, 20, 20, 10}; int value[/*items+1*/13]={48, 77, 46, 82, 85, 43, 49, 73, 65, 48, 47, 51}; </code></pre> <p>where it returned the correct output <em>7820</em>. </p> <p>But it doesn't returned the correct output when </p> <pre><code>items=9; int weight[/*items+1*/10]={60, 10, 20, 20, 20, 20, 10, 10, 10}; int value[/*items+1*/10]={73, 81, 86, 72, 90, 77, 85, 70, 87}; </code></pre> <p>where it returned the output <em>9730</em>, the correct output should be <em>14110</em>. From observation, the program somehow skipped the 1st value (weight=60, value =73). I have checked the code several times, but I just cant find what's wrong. Can someone explain to me why? Thank you!</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

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