Expert: Zlatko - 6/29/2010

Question
Hi,
I have a problem in solving this problem :
You have a bunch of N (1<=N<=10000) numbers and you want to choose some of them such that their sum is maximized, but not exceeding some limit K...
I tried alot, I think it's very close to the classic Knapsack problem, but what's the 'weight' in this case?
My recursive formula for it was something like this, I think it's rather very wrong :
dp[i][j]=max(dp[i-1][j],dp[i-1][j-num[i]]+num[i]);
The constrains are very large, which puts Brute Force and Backtracking (Which are very bad algorithms, by the way) out of the scene.
Please help me..
My previous thanks...
Regards
Abody

Answer
Edit 7 July 2010

Hello Abody
As promised:
https://docs.google.com/document/edit?id=1ahc6MXn0WSmtQFA2H4gm8baMf5eR4m12jP4uVFHST7U&hl=en

Hello Abody.
Thanks for the question. It really makes me think. Today I don't have time to actually implement a program, but for now I'd suggest that this is a 0-1 knapsack problem and dynamic programming is the correct approach. In this case, the value of the item is also its weight. You want to maximize the value but the value is not to exceed K so K is like the weight constraint.

I think your recursive formula is correct. It matches what I've seen at
http://www.cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgra...
That document probably has enough information for you to complete the program, but personally, I don't feel it makes the algorithm intuitive.

I will think about this for the next few days and I'll try to post a solution and intuitive explanation if I can develop one.

Best regards
Zlatko