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 Capacity = 100 weights = [5, 10, 20] -> Capacity = 20 weights = [1, 2, 4]
How to make the standard DP algorithm for 0/1 Knapsack make larger steps?
algorithms;optimization;dynamic programming;knapsack problems