# Does dynamic programming always add one item per sub-solution?

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 ?

• You can do whatever you want, though this could affect the running time. – Yuval Filmus Nov 1 '17 at 12:33
• @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 ? – ng.newbie Nov 1 '17 at 12:35
• Definitely not, you can also consider more elements. It just increases the running time of the algorithm. – Yuval Filmus Nov 1 '17 at 12:40
• @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 ? – ng.newbie Nov 1 '17 at 12:42
• @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. – ryan Nov 2 '17 at 1:34