Backpack Problem

The backpack problem (also known as the "Knapsack problem") is a widely known combinatorial optimization problem in computer science. In this wiki, you will learn how to solve the knapsack problem using dynamic programming.

The backpack problem can be stated as follows:

Given a set of different items, each one with an associated value and weight, determine which items you should pick in order to maximize the value of the items without surpassing the capacity of your backpack.

Concretely, imagine we have the following set of valued items and the given backpack.

Suppose you have a set of 5 items:

	First item $\hspace{5mm}$	Second Item $\hspace{5mm}$	Third Item $\hspace{5mm}$	Fourth Item $\hspace{5mm}$	Fifth Item $\hspace{5mm}$
Value: $\hspace{10mm}$	$5	$10	$3	$2	$3
Weight:	4 kg	8 kg	3 kg	5 kg	2 kg

If your backpack's weight limit is $10 \text{ kg},$ what is the optimal solution? That is, which items should you take with you?

---

In this case, the solution is clear. One would take the second and the last items, obtaining a value of $\$13$ while meeting the weight limit exactly. We achieve the maximum possible value without violating the problem's constraint. $_\square$

However, evaluating all possibilities is very unpractical in general, so we would like to know if there is a better way to approach this problem. In fact, there is, and we will see an algorithm in the next section.

This problem can be solved using simple recursion and a two-dimensional array.

To begin, we should find a convenient representation for our problem and carefully define it. We can say that we have a set of $n$ items, each item has value $v_i$ and weight $w_i$, and our bag has a total weight limit of $W$.

Now we construct an $n\times W$ table:

table1

Each cell in the table has value $t[i,j]$, where $i$ represents the $i^\text{th}$ row and $j$ represents the $j^\text{th}$ column.

$t[i,j]$ is the maximum value we can get using any combination of the set of the first $i$ items of the list without exceeding a certain weight $j$. With this, we can already identify a recursion for our table:

Recursion for the knapsack problem:

$$t[i,j]=\begin{cases}t[i-1,j] \hspace{5pt} &\text{if} \hspace{5pt} w_i>j \\ \max\big(t[i-1,j], t[i-1,j-w_i]+v_i\big)\hspace{5pt} &\text{if} \hspace{5pt} w_i \leq j. \end{cases}$$

Let's try to interpret this recursion:

Suppose you have a certain value $t[i-1,j]$ in your table, which means that the maximum value you can get using any combination of the first $i-1$ items of your list and the sum of the weight of each item does not exceed $j$. If we can do this, it's evident that we can do the same using the first $i$ items of our list. So we find the first case of our recursion, which is pretty straightforward:

$$t[i,j]=t[i-1,j] \hspace{5pt} \text{if} \hspace{5pt} w_i>j .$$

And how does the second case of the recursion work?

Given $w_i \leq j$, we can say that $t[i,j]= t[i-1,j-w_i]+v_i$ because if we can get a certain value $t[i-1,j-w_i]$ using the first $i-1$ items of the list, we can also add the $i^\text{th}$ item of the list to the backpack and it will not exceed the current limit $j$, because before we get the $i^\text{th}$ item, the current weight is $j-w_i$, so if we add the $i^\text{th}$ item the current weight will become $j-w_i+w_i=j$, so we maintain the current weight equal to the weight limit and the new value will be $t[i-1,j-w_i]$ plus the value of the item $v_i$, then $t[i,j]$ becomes $t[i-1,j-w_i]+v_i$. Nevertheless, this is not always the best option. If the value of $t[i-1,j]$ is bigger, we will use this value instead of $t[i-1,j-w_i]$. Remember $t[i,j]$ only computes the maximum value, so we will always choose the best option.

Finally, the max() function evaluates what's the best option (i.e. it finds the greatest value).

To find the greatest possible value, we just have to get $t[n,W]$ $($i.e. the maximum value possible using the $n$ items of our list while the total wight is less than the capacity $W$ of our bag$).$

Complexity of the knapsack problem

In this problem, we employ a matrix of height $n$ and width $W$, and our algorithm goes through each cell once, which makes $n\times W$ operations in total. Hence the complexity of the knapsack problem is $O(n\times W).$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

# n:number of items
# v[i]:value of the i-th item, w[i]: weight of the i-th item
# W = backpack capacity

knapsack(n,v,w,W)
    for j=0 to j=W
       t[0, j]=0 
    for i=1 to n
        for j=0 to W
            if w[i]>j 
                t[i, j]=t[i - 1, j]
            else 
                t[i, j] = max(t[i - 1, j], t[i - 1, j - w[i]]+v[i])
     return t[n][W]

Now we will solve the first example:

You are given a set of five items $I_1,I_2,I_3,I_4,I_5$and each has a corresponding value and weight inside brackets $[v_i,w_i]:$

$$I_1=[5,4],\ \ I_2=[10,8],\ \ I_3=[3,3],\ \ I_4=[2,5],\ \ I_5=[3,2].$$

What's the maximum possible value you can get, knowing that the knapsack's weight limit is $10?$

---

Let's start filling up our table:

We know that all the cells in the first row are zero, hence the following table:

table2

Using the recursion, we know that $t[1,0]=t[1,1]=t[1,2]=t[1,3]=0$. But when $j=4,$ we have $t[1,j]=t[1,4]=5$. This happens because at this point $w[i]\leq j,$ the weight of the item is $w[1]=4$ and $j=4$, so it satisfies the condition for the second case of the recursion. We know that

$$t[i-1,j]=t[0,4]=0$$

and that

$$t\big[i-1,j-w[i]\big]+v_i=t[0,0]+v_i=0+5=5.$$

Hence, the maximum here is $5$, and then $t[i,j]=t[1,4]=5$. Doing the same for $j=5$ to $j=10,$ we will also get $5,$ so our table becomes as follows:

table3

Now, $i=2.$ We will keep doing the same process. Doing the calculations, we will see that $t[2,j]=0$ from $j=0$ to $j=3$ and $t[2,j]=5$ from $j=4$ to $j=7.$ When $j=8,$ we have $w[i] \leq j,$ so we will have to analyze both cases:

$$t[i-1,j]=t[1,8]=5$$

and

$$t\big[i-1,j-w[i]\big]+v_i=t[1,0]+v_i=0+10=10.$$

The second option is the best one, so

$$t[i,j]=t[2,8]=10.$$

Doing the same until we finish the row, we get

table4

Just keep using the recursion to fill up the third and the fourth rows until you get to the last one:

table5

When you reach $t[5,9],$ you will see

$$t[i-1,j]=t[4,9]=10$$

and

$$t\big[i-1,j-w[i]\big]+v_i=t[4,7]+v_i=8+3=11.$$

For the last cell

$$t[i-1,j]=t[4,10]=10$$

and

$$t\big[i-1,j-w[i]\big]+v_i=t[4,8]+v_i=10+3=13.$$

Therefore $t[i,j]=t[5,10]=13$.

This is our complete table:

The maximum value we can get is $t[n,W]=t[5,10]=13$, which can be achieved using the second and the last items. By doing this, the total weight will be $10$ (it's equal to the capacity, which is 10) and the total value will be $13.$

Here's a sample code you can use to solve the problem:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

#include <iostream> #include <cstring> /*Knapsack problem*/ //W=Backpack capacity //w[i]=i-th item's weight //v[i]=i-th item's value //Compares two values and returns the bigger one int maximum(int a,int b){ if(a>=b) return a; else return b; } using namespace std; int main() { int W, v[100],w[100]; int i,j,n; int table[100][10000]; //Reads W and the number of items n cin>>W>>n; //Reads the weight and the value of each item for(i=1;i<=n;i++) { cin>>w[i]>>v[i]; } //Make every single cell in the first row equal to zero for(j=0;j<=W;j++) table[0][j]=0; // Fills the table for(i=1;i<=n;i++) for(j=0;j<=W;j++){ //First case of the recursion if(w[i]>j) table[i][j]=table[i-1][j]; //Second case else table[i][j]=maximum(table[i-1][j],table[i-1][j-w[i]] + v[i]); } cout<<"\n"; //Shows the table for(i=0;i<=n;i++){ cout<<"\n"; for(j=0;j<=W;j++){ cout<<table[i][j]<<" "; } } //Prints the answer cout<<"\nMaximum value:\n"; cout<<table[n][W]; cout<<"\n\n"; return 0; }

Though simply stated and simply solved, the knapsack problem can be mapped directly, if not used as a prototype for numerous practical problems. Direct applications include the following:

• a shipping company trying to pack as much package volume into a transport plane without breaking the weight capacity,
• a professional sports team's desire to build a team that meets various statistical projections without breaking the salary cap, and
• Soylent's need to satisfy daily nutritional requirements while maintaining a given powder volume per serving.

More interesting applications include the following:

• Hedge fund's need to invest so as to maximize potential gains, while keeping the value at risk (VaR) below a given threshold.
• The formation of gerrymandered political districts. Each town has a population $p_i$, and a fraction $f_i$ of its population that votes for party $A$. The political group (political party A) that controls district selection wants to make a district with the quantity $\dfrac{\sum_i p_i f_i}{\sum_ip_i}$ as large as possible while keeping the total number of people below some limit and maintaining a contiguous set of towns.

Constrained optimizations are some of the most common puzzles in managing all kinds of operations. Given the simplicity of its setup, the variety of techniques available to solve it, and its direct application to real problems, the knapsack problem is an excellent toy model and serves as a rich training ground for more advanced problems in optimality.