4
$\begingroup$

As we know Dynamic programming has two techniques.

  1. Bottom up dynamic programming approach.
  2. Top down memoization approach

Normally dynamic knapsack problem is solved using Bottom up dynamic programming approach.can we solve dynamic knapsack problem using Memoization approach?

enter image description here

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Have you tried using this approach? Were you successful? $\endgroup$ – Yuval Filmus Jul 10 '16 at 16:24
  • $\begingroup$ yes I tried it with bottom up dynamic approach and It was successful.It gives 0(nW) time complexity (n=number of items,W=knapsack limit) $\endgroup$ – dulaj sanjaya Jul 10 '16 at 16:45
  • $\begingroup$ How does the other approach compare? What does it give? $\endgroup$ – Yuval Filmus Jul 10 '16 at 16:54
  • $\begingroup$ According to this image memoization technique filling the table recursively by results of earlier calls.So can we develop knapsack problem using that technique $\endgroup$ – dulaj sanjaya Jul 10 '16 at 17:09
  • $\begingroup$ In bottom up approach- Yes.It is working. suppose that name of the 2D array is V. Then v[n][w] gives the correct answer.(doesn't need to full the knapsack) $\endgroup$ – dulaj sanjaya Jul 10 '16 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.