Imagine that you and your friends are planning a hiking trip in the wilderness for a few days. As you prepare for the trip, you realize that you'll need to bring all the essentials like food, water, camping gear, and clothing, but your backpack has a limited weight capacity. So you decide to assign a value based on the importance of that item relative to the other items for example water has a higher value than extra clothing. But each item has a different weight alongside their importance value. So now you start to wonder, how can you optimize your backpack's contents to carry the most valuable items while staying within the weight limit? You soon discover that this is a classic problem called the knapsack problem!

The bounded knapsack problem is to fit as many valuable items into a limited space as possible while maximizing the sum total value of the items. In your case, the limited space is the weight capacity of your backpack, and the valuable items are the things you need to survive in the wilderness. As you begin to plan and pack for your trip, you realize that some items have a higher value to you, such as food and water, while others are less valuable, like an extra pair of shoes. But some of the less valuable items may still be necessary for the trip. So, you need to figure out how to balance the weight and value of each item to make the most of your backpack's limited capacity. This is where the knapsack problem gets tricky, as you need to consider both the weight and value of each item to decide what to pack. You might have to make some tough choices about what to include and what to omit.

Let's try to solve this problem with the following weights and values. Recall that the task is to select items from the given set, where each item has a weight and a value, such that the total weight of the selected items is within a specified limit and the total value is maximized. Select a combination of items by clicking them to put them in the backpack. Click the items again in the backpack if you want to remove items from it.

Hint: the highest possible total value within the weight capacity is 34. See if you can get this value!

Backpacker's Playground

Let's break this problem down, starting from the naive approach and then considering more advanced techniques!

Brute Force Approach

Naively solving the knapsack problem involves trying out all possible combinations of items that fit within the weight limit of the backpack and then selecting the one with the highest value. However, the brute force approach becomes impractical for large input sizes since the number of possible combinations grows exponentially. For small input sizes though, brute force can be a viable option. We can simply enumerate all possible combinations of items and their corresponding weights and values, checking each to see if it fits within the weight limit of the backpack and calculating its total value. Among the valid combinations, we can select the one with the highest total value.

We can enumerate the possible combinations recursively. Given items \(1\ldots n\) and weight capacity \(W\), we consider two cases for item \(n\): either it's included in the backpack or it's not included. In the animation below the left path is when it is not included and the right path is when it is included.

If the item is included, we increase our value by \(\texttt{value}(n)\). Then, we recursively solve the subproblem with items \(1\ldots n-1\)
with weight capacity \(W - \texttt{weight}(n)\).
If the item is not included, we recursively solve the subproblem with items \(1\ldots n-1\) with weight capacity still at \(W\).

The best solution for the original problem with items \(1 \ldots n\) is just the one that yields the higher value among the two subproblems. We continue this process until there are no more items to consider, where the only total value possible is 0.

The animation below demonstrates this algorithm. Note that with 10 items, the tree extends much further than what is shown. The lowest level for the tree would be when \(n=0\) meaning all items have been considered for that pathway.

Notice in the third level of the tree, we have two distinct nodes that represent the same subproblem of \(n=8, W = 7\). The subtrees rooted at each of these nodes are identical. Despite having solved the same subproblem before, the algorithm will recurse until it reaches the leaves of the tree, which is unnecessary. To improve the efficiency of the recursive approach, we can memoize the results of subproblems we computed by storing them in a table. Before solving any subproblem, we check the table and if the result is already there, we simply retrieve it from the table instead of recalculating it. This technique is known as dynamic programming.

Bottom-Up Approach with Animation

The bottom-up approach is simply another way to implement dynamic programming. In this approach, we solve the smallest subproblems first before solving larger subproblems. For any subproblem we are currently solving, we are guaranteed that all smaller subproblems have been solved before. We create a table with the columns representing weight capacities \(0\ldots W\) and the rows representing the \(n\) items. The value in the \(i\)th row and \(j\)th column represents the maximum total value possible choosing from items \(1\ldots i\) such that the items chosen don't exceed weight limit \(j\).

We first fill the row \(i=0\), where there are no items to consider. We gradually fill in the remaining cells of the table in increasing order of \(i\) and increasing order of \(j\). For each cell, we consider the same two cases and select the one that yields higher value:

We add \(\texttt{value}(i)\) and solve the sub-problem with items \(1\ldots i-1\) and weight limit \(j-\texttt{weight}(i)\).
We solve the sub-problem with items \(1\ldots i-1\) and weight limit \(j\).

The animation below will demonstrate this algorithm. The table is filled row by row. At each cell, the algorithm checks if the current item \(i\) can be included within the weight limit \(j\). If it can be included, the algorithm checks whether including it would yield a higher value than the best value for items \(1\ldots i-1\) and same weight limit \(j\). If so, we choose the former. If the current item cannot be included within the weight limit, then the algorithm simply copies the best value for items \(1\ldots i-1\) and same capacity \(j\). Once the table is filled, the maximum value that can be obtained while staying within the weight limit is found in the bottom-right cell of the table. The items that were selected to obtain this value can be traced back from the table by examining the cells that contributed to the final value.

Press Play to watch the animation or press Step to watch the algorithm fill one cell in the table at a time.

Play Speed:


Item Index \(i\)	\(\texttt{weight}(i)\)	\(\texttt{value}(i)\)	1	2	3	4	5	6	7	8	9	10
-			0	0	0	0	0	0	0	0	0	0
1			0	0	0	0	0	0	0	0	0	0
2			0	0	0	0	0	0	0	0	0	0
3			0	0	0	0	0	0	0	0	0	0
4			0	0	0	0	0	0	0	0	0	0
5			0	0	0	0	0	0	0	0	0	0
6			0	0	0	0	0	0	0	0	0	0
7			0	0	0	0	0	0	0	0	0	0
8			0	0	0	0	0	0	0	0	0	0
9			0	0	0	0	0	0	0	0	0	0
10			0	0	0	0	0	0	0	0	0	0

Algorithm Code

Now we will explain the code for solving the knapsack problem using the bottom up dynamic programming approach. We will refer to the code block below.


    function knapsack(weights, vals, weightLimit) {

        // Calculate the number of items
        let numItems = weights.length;

        // Creating 2d array (weightLimit + 1) x (numItems + 1)
        let table = new Array(numItems + 1);

        // Initialize the table with 0 values
        for (let i = 0; i <= numItems; i++) {
            table[i] = new Array(weightLimit + 1).fill(0);
        }

        // Solving sub-problems in a bottom-up approach manner
        for (let i = 1; i <= numItems; i++) {
            for ( let j = 0 j <= weightLimit; j++) {
                // If the current item cannot be included, use the previous item’s value
                if (weights[i - 1] > j) {
                    table[i][j] = table [i - 1][j];
                } else {
                    // Choose the maximum value between including or excluding the current item
                    table[i][j] = Math.max(table[i - 1][j], table[i - 1][j - weights[i - 1]] + vals[i - 1]);
                }
            }
        }

        // Displaying the output table
        return table;
    }


    public int[][] knapsack(int[] weights, int[] vals, int weightLimit) {

        // Calculate the number of items
        int numItems = weights.length;

        // Create a 2d array (weightLimit + 1) x (numItems + 1)
        int[][] table = new int[numItems + 1][weightLimit + 1];

        // Solving sub-problems in a bottom-up approach manner
        for (int i = 1; i <= numItems; i++) {
            for (int j = 0; j <= weightLimit; j++) {
                if (weights[i - 1] > j) {
                    table[i][j] = table[i-1][j];
                } else {
                    table[i][j] = Math.max(table[i - 1][j], table[i - 1][j - weights[i - 1]] + vals[i - 1]);
                }
            }
        }

        // Displaying the output table
        return table;
    }


    # add "import math"

    def  knapsack(self, weights,  vals,  weightLimit) :

        # Calculate the number of items
        numItems = len(weights)

        # Create a 2d array (weightLimit + 1) x (numItems + 1)
        table = [[0] * (weightLimit + 1) for _ in range(numItems + 1)]

        # Solving sub-problems in a bottom-up approach manner
        i = 1
        while (i <= numItems) :
            j = 0
            while (j <= weightLimit) :
                if (weights[i - 1] > j) :
                    table[i][j] = table[i - 1][j]
                else :
                    table[i][j] = max(table[i - 1][j],table[i - 1][j - weights[i - 1]] + vals[i - 1])
                j += 1
            i += 1
        return table

The function \(\texttt{knapsack}\) takes three inputs: a \(\texttt{weights}\) array, a \(\texttt{vals}\) array, and a \(\texttt{weightLimit}\). The function first creates a 2D array with dimensions \(\texttt{numItems+1} \times \texttt{weightLimit+1}\) and initializes all values to 0.

Then, the function uses a nested loop to fill in the \(\texttt{table}\). The outer loop iterates through each item in the \(\texttt{weights}\) and \(\texttt{vals}\) arrays, while the inner loop iterates through each possible weight up to the weightLimit. For each cell in the table, the function considers two cases: either the item is not included in the backpack, or it is included in the backpack. If the weight of the item is greater than the current weight limit, the function copies the value from the cell above it in the table. If the weight of the item is less than or equal to the current weight limit, the function compares the value of including the item with the value of not including the item and selects the maximum.

Finally, the function returns the completed table, which contains the maximum value that can be obtained for each weight and item combination. The function does not select the actual items to include in the backpack, but it provides the necessary information to do so.

If you are interested in learning more about dynamic programming, look into related concepts of memoization, top-down vs bottom-up approach, state space reduction, approximation algorithms and related problems of longest common subsequence (LCS) problem, matrix chain multiplication, edit distance, Bellman-Ford algorithm, Floyd-Warshall algorithm, coin change problem, 0/1 knapsack problem.

Backpacker's Dilemma: The Bounded Knapsack Problem

Backpacker's Playground

Brute Force Approach

Bottom-Up Approach with Animation

Algorithm Code