Clever Geek Handbook

How to optimize the solution for backpack 0/1?

The standard solution to the backpack problem O(nW)

, where we will increase the weight +1 at a time to get to the solution.

Is there any approach to the knapsack problem that doesn't require a +1 weight gain at a time.

eg. One way I can think of is to divide all the numbers by your common denominator

Capacity = 100 weights = [5, 10, 20] -> Capacity = 20 weights = [1, 2, 4]

+3


source to share


1 answer


Increasing the weight in increments of 1 is only necessary for dynamic bottom-up programming. If you implement it from top to bottom, you can simply make a recursive call, subtracting the weight of the current item from the remaining capacity.



0


source






More articles:


All Articles