In the 0-1 knapsack problem, I am given a set of items with their weights and the weight that a knapsack can carry.

The objective is to maximize the number of items I can carry subject to the fact that I do not exceed the maximum weight of the knapsack.

The algorithm could be something as follows-:

weight = 0
list_of_items = {}
while weight < max_weight
for all remaining items present find one item that is equal to (weight + 1)
repeat until weight > max_weight

The key word here is "find one item".

This is my question, is it always true that we search for only 1 item each iteration for the next state/sub-solution ? Or can we search for multiple items ?

Will the next sub-solution always contain 1 value more than the previous one if it is possible to achieve ?

  • $\begingroup$ You can do whatever you want, though this could affect the running time. $\endgroup$ – Yuval Filmus Nov 1 '17 at 12:33
  • $\begingroup$ @YuvalFilmus Most dynamic programs that I have seen till now only search for 1 new item to add the previous sub solution found. Wondering if that is the only way to go about constructing the ultimate optimal solution ? $\endgroup$ – ng.newbie Nov 1 '17 at 12:35
  • $\begingroup$ Definitely not, you can also consider more elements. It just increases the running time of the algorithm. $\endgroup$ – Yuval Filmus Nov 1 '17 at 12:40
  • $\begingroup$ @YuvalFilmus yeah thats kind of my point. The optimal way of doing it is considering 1 new element per sub solution, right ? Considering more wouldn't be the correct/optimal way, right ? $\endgroup$ – ng.newbie Nov 1 '17 at 12:42
  • $\begingroup$ @ng.newbie It would be difficult to prove that anyway to solve it is optimal considering knapsack's an NP-hard problem. It may be asymptotically better to choose 1 item at a time, however, probably not provably optimal. $\endgroup$ – ryan Nov 2 '17 at 1:34

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.