Recently I've came across an interesting DP problem.Here it is . This problem seem very hard to a newbie like me, because W (weight allowed of the bag) <= 10^9. So i came up with a solution (obviously wrong, that why I'm asking u guys ^_^) : I define a function f(i, j), which return the minimum weight we need to add to archive a j value (We will call this value dp[i][j]). I have 2 arrays : wt[i ... n] for weights and val[i ... n] for values (n <= 100). Finally I have ans = 0;(this is the answer of course); If wt[i] <= W (mean we can take only this item), I will have dp[i][j] = min(f(i-1, j), f(i-1, j-val[i])+wt[i]); So if at this point, dp[i][j] still <= W, I'll have ans = max(ans, j); If (wt[i] > W) (well mean I can't pick it) I will have dp[i][j] = f(i-1, j); return dp[i][j];
So my question : "Where did i screw up ???". I'm wrong, so how is this problem supposed to be solved ?? // Thank for taking your time reading this anyway, and if u can help, I'm always open to be corrected.
vi <= 10^3 and N <=100 , try to see if we can make vj for j = 1...sum of all vi's.
Instead of thinking about the max value you can get for a fixed weight . Think about the minimum weight for which you can get that value.