Suppose the usual dynamic programming algorithm for the knapsack problem. If we swap the max with an addition, does the modified algorithm compute all the solutions with benefit $\leq W$? I described the problem very briefly but I think anyone familiar with these notion wouldn't find any difficulty understanding what I ask. I think the complexity stays $nW$. Is it right?

  • 1
    $\begingroup$ You mention that you think that everything works. If so, it seems like you already know the answer. Do you have any specific doubts? $\endgroup$ – Yuval Filmus Mar 10 '15 at 19:53
  • $\begingroup$ My main doubt is that the idea appears too simple. More precisely, if the optimization problem can be computed exactly in $nW$ it seems like we get the answer to the counting problem for free. $\endgroup$ – Paramar Mar 10 '15 at 19:57
  • 3
    $\begingroup$ This is often the case in dynamic programming, for the reason you mention (you can replace $\max$ or $\lor$ with $+$). $\endgroup$ – Yuval Filmus Mar 10 '15 at 20:08
  • 1
    $\begingroup$ Answers that allow only "yes" as an answer are not good for the site. If you have a specific question about your approach, please flesh out your post. $\endgroup$ – Raphael Mar 11 '15 at 7:15
  • $\begingroup$ In addition -- what have you tried, and where did you get stuck? The obvious way to answer your question on your own is to try to prove the algorithm correct (say, by induction). Have you tried that? If not, you should try it -- we expect you to make a significant effort before asking, and to show us what you've tried. $\endgroup$ – D.W. Mar 11 '15 at 16:37

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.