arius1408's blog

By arius1408, history, 6 weeks ago,

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.

Read more »

• 0

By arius1408, history, 3 months ago,

Recently, I've came across a DP problem. Problem 455A After a while I can't seem to think of any solution so i read the tutorial. Then i've totally lost. I can't understand how the solution work. Anyone can help me ?

P/s : And if you can explain me why could people come up with that solution ( I mean their thoughts process ), that would be a huge help. Anyway, help me pls. I'm stuck !!!

// If anything, forgive me for my bad english. I'm not a native speaker.

Read more »

• +1