DSA The 0/1 Knapsack Problem

The 0/1 Knapsack Problem states that you have a backpack with a weight limit, and you are in a room full of treasures, each treasure with a value and a weight. To solve the 0/1 Knapsack Problem you must figure out which treasures to pack to maximize the total value, and at the same time keeping below the backpack's weight limit. Bravo! You found the items that gives the maximum value😀

$ / kg

$ kg Are you able to solve the 0/1 Knapsack Problem above manually? Continue reading to see different implementations that solves the 0/1 Knapsack Problem. Solving the 0/1 Knapsack Problem helps businesses decide which projects to fund within a budget, maximizing profit without overspending. It is also used in logistics to optimize the loading of goods into trucks and planes, ensuring the most valuable, or highest prioritized, items are included without exceeding weight limits.

Every item has a weight and value. Your knapsack has a weight limit. Choose which items you want to bring with you in the knapsack. You can either take an item or not, you cannot take half of an item for example.

Maximize the total value of the items in the knapsack.

Using brute force means to just check all possibilities, looking for the best result. This is usually the most straight forward way of solving a problem, but it also requires the most calculations.

Calculate the value of every possible combination of items in the knapsack. Discard the combinations that are heavier than the knapsack weight limit. Choose the combination of items with the highest total value.

Consider each item one at a time. If there is capacity left for the current item, add it by adding its value and reducing the remaining capacity with its weight. Then call the function on itself for the next item. Also, try not adding the current item before calling the function on itself for the next item. Return the maximum value from the two scenarios above (adding the current item, or not adding it).

values = [300, 200, 400, 500] weights = [2, 1, 5, 3]

Running the code above means that the knapsack_brute_force function is called many times recursively. You can see that from all the printouts.

If we run out of items to check ( n==0 ), or we run out of capacity ( capacity==0 ), we do not do any more recursive calls because no more items can be added to the knapsack at this point.

If the current item is heavier than the capacity (

), forget the current item and go to the next item.

If the current item can be added to the knapsack, see what gives you the highest value: adding the current item, or not adding the current item. Running the code example creates a recursion tree that looks like this, each gray box represents a function call:

knapsack(10,4):

knapsack(7,3):

knapsack(10,3):

knapsack(2,2):

knapsack(7,2):

knapsack(5,2):

knapsack(10,2):

knapsack(2,1):

knapsack(6,1):

knapsack(7,1):

knapsack(4,1):

knapsack(5,1):

knapsack(9,1):

knapsack(10,1):

In the recursion tree above, writing the real function name knapsack_brute_force(7,3) would make the drawing too wide, so "ks(7,3)" or "knapsack(7,3)" is written instead. From the recursion tree above, it is possible to see that for example taking the crown, the cup, and the globe, means that there is no space left for the microscope (2 kg), and that gives us a total value of 200+400+500=1100. We can also see that only taking the microscope gives us a total value of 300 (right bottom gray box). As you can see in the recursion tree above, and by running the example code, the function is sometimes called with the same arguments, like knapsack_brute_force(2,0) is for example called two times. We avoid this by using memoization.

The memoization technique stores the previous function call results in an array, so that previous results can be fetched from that array and does not have to be calculated again. Read more about memoization here. Memoization is a 'top-down' approach because it starts solving the problem by working its way down to smaller and smaller subproblems. In the brute force example above, the same function calls happen only a few times, so the effect of using memoization is not so big. But in other examples with far more items to choose from, the memoization technique would be more helpful.

In addition to the initial brute force code above, create an array memo to store previous results. For every function call with arguments for capacity c and item number i, store the result in memo[c,i]. To avoid doing the same calculation more than once, every time the function is called with arguments c and i, check first if the result is already stored in memo[c,i]. After improving the brute force implementation with the use of memoization, the code now looks like this:

if n == 0 or capacity == 0:

values = [300, 200, 400, 500] weights = [2, 1, 5, 3]

The highlighted lines in the code above show the memoization technique used to improve the previous brute force implementation.

Create an array memo where previous results are stored.

At the start of the function, before doing any calculations or recursive calls, check if the result has already been found and stored in the memo array.

Store the result for later.

Another technique to solve the 0/1 Knapsack problem is to use something called tabulation. This approach is also called the iterative approach, and is a technique used in Dynamic Programming. Tabulation solves the problem in a bottom-up manner by filling up a table with the results from the most basic subproblems first. The next table values are filled in using the previous results.

Consider one item at a time, and increase the knapsack capacity from 0 to the knapsack limit. If the current item is not too heavy, check what gives the highest value: adding it, or not adding it. Store the maximum of these two values in the table. In case the current item is too heavy to be added, just use the previously calculated value at the current capacity where the current item was not considered. Use the animation below to see how the table is filled cell by cell using previously calculated values until arriving at the final result. Find the maximum value in the knapsack. Click "Run" to fill the table. After the table is filled, click a cell value to see the calculation. Weights (kg) Knapsack capacities (kg) Values ($) Oi!

↓ + =

$