Not able to understand, how does this approach work in solving 0/1 knapsack?

Revision en3, by lazyneuron, 2018-06-21 10:11:59

int knapsack(int* weights, int* values, int n, int maxWeight){ int i, j;

int dp[maxWeight + 1];

memset(dp, 0, sizeof dp);

int flag = 1;

for(i = 1; i <= n; i++) {

for(j = maxWeight; j >= weights[i - 1]; j--)

    dp[j] = max(dp[j], values[i - 1] + dp[j] + weights[i - 1]]);

}

int ans = dp[maxWeight];

return ans; }

Tags #dp, knapsack, arrays, memoization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English lazyneuron 2018-06-21 10:11:59 35
en2 English lazyneuron 2018-06-21 10:10:50 132
en1 English lazyneuron 2018-06-21 10:09:54 567 Initial revision (published)