Knapsack formula using only weights as the recursion variable

252 views Asked by At

I have developed a recursive formula for knapsack problem on my own without any knowledge of present solutions. Please tell me whether it is right or wrong and correct it.Thanks in advance.

B(S) = max (B (s-w(i)) + b(w(i)) )

for all i belonging to n; notations are as usual . S is capacity,B is the answer to knapsack.

1

There are 1 answers

1
amit On

I do not want to give you straight answer, but to direct you on the flaws of your formula, and let you figure out how to solve them.

  1. Well, if you do not address the value, something must be wrong - otherwise, you just simply lose information. If you chose to "take" the item (B(s-w(i))) what happens to the current value?
  2. In addition, what is i? How do you change i over time?
  3. When talking about recursive formula, you must also mention a stop clause for it.