Not able to understand, how does this approach work in solving 0/1 knapsack?
Difference between en1 and en2, changed 132 character(s)
#include<bits/stdc++.h>↵
using namespace std;↵
int knapsack(int* weights, int* values, int n, int maxWeight){↵
ios_base :: sync_with_stdio(false);↵
cin.tie(NULL), cout.tie(NULL);↵
  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 &mdash; 1]; j--)↵
↵
        dp[j] = max(dp[j], values[i &mdash; 1] + dp[j &mdash; weights[i &mdash; 1]]);↵
↵
  }↵
↵
  int ans = dp[maxWeight];↵
↵
  return ans;↵
}↵

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)