The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

Example of a one-dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kg?

knapsack problem

Definition

0/1 knapsack problem

The most common problem being solved is the 0/1 knapsack problem, which restricts the number $x_i$ of copies of each kind of item to zero or one.

Given a set of n items numbered from $1$ up to $n$, each with a weight $w_i$ and a value $v_i$, along with a maximum weight capacity $W$,

maximize \(\sum_{i=1}^{n} v_i x_i\)

subject to \(\sum_{i=1}^{n} w_i x_i \leq W\) and $x_i \in {0, 1}$ for all $i = 1, 2, \ldots, n$.

Here $x_i$ represents the number of instances of item $i$ to include in the knapsack. Informally, the problem is to maximize the sum of the values of the items in the knapsack so that the sum of the weights is less than or equal to the knapsack’s capacity.

Bounded knapsack problem (BKP)

The bounded knapsack problem (BKP) removes the restriction that there is only one of each item, but restricts the number $x_i$ of copies of each kind of item to a maximum non-negative integer value $c$:

maximize \(\sum_{i=1}^{n} v_i x_i\)

subject to \(\sum_{i=1}^{n} w_i x_i \leq W\) and $0 \leq x_i \leq c$ for all $i = 1, 2, \ldots, n$.

Unbounded knapsack problem (UKP)

The unbounded knapsack problem (UKP) places no upper bound on the number of copies of each kind of item and can be formulated as above except for that the only restriction on $x_i$ is that it is a non-negative integer.

maximize $\sum_{i=1}^{n} v_i x_i$

subject to $\sum_{i=1}^{n} w_i x_i \leq W$ and $x_i \geq 0$ for all $i = 1, 2, \ldots, n$.

References

Implementations

  • 1

    # TODO: Implement in Python

  • 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

    const val = [1, 4, 5, 7]; // The value of all available items
const wt = [1, 3, 4, 5]; // The weights of available items
const W = 7; // The maximum weight we can carry in our collection
const N = val.length;
const DP = new Array(N + 1);

for (let i = 0; i < N + 1; i++) {
  DP[i] = new Array(W + 1);
  for (let j = 0; j < W + 1; j++) {
    DP[i][j] = 0;
  }
}

for (let i = 0; i <= N; i++) {
  for (let j = 0; j <= W; j++) {
    if (i === 0 || j === 0) {
      /*
      If we have no items or maximum weight we can take in collection is 0
      then the total weight in our collection is 0
      */
      DP[i][0] = 0;
      
    } else if (wt[i - 1] <= j) { // take the current item in our collection
      
      const A = val[i - 1] + DP[i - 1][j - wt[i - 1]];
      const B = DP[i - 1][j];
      /*
      find the maximum of these two values
      and take which gives us a greater weight
       */
      if (A > B) {
        DP[i][j] = A;
        
      } else {
        DP[i][j] = B;
        
      }
      
    } else { // leave the current item from our collection
      DP[i][j] = DP[i - 1][j];
      
    }
  }
}

console.log(` Best value we can achieve is ${DP[N][W]}`);