Tabular form simplest and remeber this as used in many problems


#1

int Solution::solve(vector &values, vector &weights, int C) {
int n=values.size();
if(n==0 || C==0)
return 0;
int dp[n+1][C+1];
memset(dp,0,sizeof(dp)); // fully filling zero
for(int i=1;i<=n;i++)
{
for(int j=1;j<=C;j++)
{
if(j < weights[i-1])
dp[i][j]=dp[i-1][j];
else
{
dp[i][j]=max(dp[i-1][j-weights[i-1]]+values[i-1],dp[i-1][j]);
}
}
}
return dp[n][C];
}