The standard knapsack problem solution is O(nW) where we will increment the weight +1 at a time to get to the solution.
Is there any approach to the knapsack problem that does not require incrementing weight +1 at a time.
e.g. One way that I can think of is to divide all the numbers by its common denominator
Capacity = 100 weights = [5, 10, 20] -> Capacity = 20 weights = [1, 2, 4]
Incrementing the weight in steps of 1 is only necessary for a bottom-up dynamic programming implementation. If you implement it top-down, you can just do a recursive call while subtracting the weight of the current item from the remaining capacity.