### shank_punk's blog

By shank_punk, 7 years ago,

How do I solve This problem efficiently ?

• +7

 » 7 years ago, # | ← Rev. 2 →   +7 It's classical DP problem. a[0] = true; for (int i = 0; i < n; ++i) for (int j = W; j >= 0; --j) if (a[j]) a[j + w[i]] = true; 
•  » » 7 years ago, # ^ |   0 Thanks . Is there a better algorithm than knapsack ?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 My bad, I'm sorry.
•  » » » 7 years ago, # ^ |   +1 N<=20
•  » » » » 7 years ago, # ^ |   +5 Oh yeah this line confused me, sorry:1 <= weight of each vegetable <= 1000