0-1背包问题：NP完全性和伪多项式时间可解

1. Overview

The knapsack problem is an old and popular optimization problem. In this tutorial, we’ll look at different variants of the Knapsack problem and discuss the 0-1 variant in detail.

Furthermore, we’ll discuss why it is an NP-Complete problem and present a dynamic programming approach to solve it in pseudo-polynomial time.

2. General Definition

Given a knapsack with a weight limit of , a collection of items x_1, x_2, x_3, ... , x_n with values v_1, v_2, v_3, ..., v_n and weights w_1, w_2, w_3, ..., w_n , the knapsack problem is defined as the optimization problem:

$[ \max \Sigma_{i=1}^{n} x_iv_i ]$

$[ \textrm{s.t.} \Sigma_{i=1}^{n} x_iw_i \leq W ]$

Now, the question is, what is the maximum value of the items that can be added to the knapsack such that the weight does not exceed the weight limit $\mathbf{W}$ ?

3. Variants of Knapsack Problem

There are three variants of the above knapsack problem depending on how x_1, x_2, x_3, ..., x_n are defined. In this section, we’ll discuss these variants of this problem.

3.1. 0-1 Knapsack Problem

In this variant, the items are defined as: $x_i \in \{0,1\}, \ \forall\ i=1,2,..,n$

Here, there is only one of each item available. So if x_i is $\mathsf{0}$ , that means the item is not added to the knapsack. If x_i is , that means the item is added to the knapsack.

3.2. Bounded Knapsack Problem

In this case, the items are bounded by the condition: $0 \leq x_i \leq c, \ \forall\ i=1,2,..,n$

The variable denotes the number of available copies of each item.

3.3. Unbounded Knapsack Problem

Here, the items are in the form: $x_i \geq 0, \forall\ i=1,2,...,n$

In unbounded knapsack, there is no bound on the number of items. There are unlimited copies of each item available.

4. Why 0-1 Knapsack Problem Is NP-Complete?

The decision version of the 0-1 knapsack problem is an NP-Complete problem. Let’s see why.

Given weights and values of items, and , respectively, can a subset of items $X \subseteq \{1,2,..,n\}$ be picked that satisfy the following constraints:

$[\Sigma_{i \in X} v_i \geq V ]$

$[\Sigma_{i \in X} w_i \leq W]$

A ‘Yes’ or ‘No’ solution to the above decision problem is NP-Complete. Solving the above inequalities is the same as solving the Subset-Sum Problem, which is proven to be NP-Complete. Therefore, the knapsack problem can be reduced to the Subset-Sum problem in polynomial time.

Further, the complexity of this problem depends on the size of the input values v_i's , w_i's . That is, if there is a way of rounding off the values making them more restricted, then we’d have a polynomial-time algorithm.

This is to say that the non-deterministic part of the algorithm lies in the size of the input. When the inputs are binary, it’s complexity becomes exponential, hence making it an NP-Complete problem.

5. Dynamic Programming Algorithm

In this section, we’ll discuss a dynamic programming approach for solving the 0-1 knapsack problem.

Let’s start by presenting its pseudocode:

algorithm ZeroOneKnapsack(W, v, w, n):
    // INPUT
    //    W = the weight limit of the knapsack
    //    v = values of the items, indexed from 1 to n
    //    w = weights of the items, indexed from 1 to n
    //    n = the number of items
    // OUTPUT
    //    the maximum value that can be achieved within weight W

    M <- initialize an (W + 1) times (n + 1) matrix
    for w <- 0 to W:
        M[0, w] <- 0
    for i <- 0 to n:
        M[i, 0] <- 0

    for i <- 1 to n:
        for w <- 1 to W:
            if w[i] <= w:
                M[i, w] <- max(M[i - 1, w - w[i]] + v[i], M[i - 1, w])
            else:
                M[i, w] <- M[i - 1, w]

    return M[n, W]

Here, first, the algorithm creates a matrix of size $((n+1)\times (W+1))$ .

Every entry M[i,w] denotes the maximum value the knapsack can take with a particular weight limit and items. We iterate over all possible weights (along the column) up to the weight limit and then pick a new item (next row) to see how the value of the knapsack increases.

To compute the maximum value at any given position in the matrix:

If : $\ M[i,w] = M[i-1,w]$
If $w_i \leq w$ : $M[i,w] = max(M[i-1,w-w_i]\ +\ v_i,\ M[i-1,w])$

The function M[i-1, w] denotes the value at the position right above the current position (i-1, w) , to check without adding the item , and M[i-1,w-w_i]+v_i presents the value of the knapsack if the current item is added.

A general idea is to pick the current item, which is the $i^{th}$ item (for a given weight limit if the first term in the max() function above is more than the second). The second term represents the total value at weight capacity if we do not pick the $i^{th}$ item.

6. An Example

Now, as we are done discussing the dynamic approach for the 0-1 knapsack problem, let’s run the algorithm on an example:

We can only carry 10kgs in our grocery bag. We’re interested in finding what would be the maximum value (say calories here) of all the items in the bag combined.

For this example, we’ve already defined the weights and values:

$[ W = \{1,2,1,3,5\} ]$

$[ V = \{10,40,20,20,60\}]$

Now, according to the algorithm, the first step is to initialize the matrix, , with the first row and the first column entries to zeros.

After the initialization of the matrix , it’s time to start the iteration step.

Let’s start the first loop. For the values: $i = 1,\ w=1,\ w_i=1,\ v_i=10,\ w_i \leq w$ :

$[M[1,1] = max(M[0,0] + 10,\ M[0,1]) ]$

[ M[1,1] = 10]

It can be verified that M[1,w] = 10 for $2 \leq w \leq 10$ because $w_1 \leq w$ in that interval:

[M[1,w] = max(M[0,w-w_1] + 10, M[0,w])]

$[ M[0,w] = 0,\ M[0,w-w_1]=0\ \forall\ 2 \leq w \leq 10]$

weight capacity $\rightarrow$

weights

values

Let’s discuss the result in the table. Our first column is $\mathsf{0}$ . It denotes that if the total weight is $\mathsf{0}$ , no matter what item we choose, the maximum knapsack value is always $\mathsf{0}$ .

Next, we choose the weight equals . With the value of , the maximum we can get is . So we filled all the rows with a maximum knapsack value of .

Now, let’s start the second loop.

For the values $i = 2,\ w=1,\ w_i=2,\ v_i=40,\ w_i > w$ :

[M[2,1] = M[1,1] ]

For the other values, we’ll increase the value of and keep everything else unchanged. We’ll start the loop with the values $i = 2,\ w=2,\ w_i=2,\ v_i=40,\ w_i \leq w$ :

$[M[2,2] = max(M[1,0] + 40,\ M[1,2]) = max(40,10) = 40 ]$

Inside the max function were two choices – to either pick item # (in such case, the value of item # gets added) or to leave it.

Again, for $i = 2,\ w=3,\ w_i=2,\ v_i=40,\ w_i \leq w$ :

$[M[2,3] = max(M[1,1] + 40,\ M[1,3]) = max(10+40,10) = 50 ]$

$M[2,w] = 50,\ \forall\ 4 \leq w \leq 10$ because $w_2 \leq w$ in that interval:

[M[2,w] = max(M[1,w-w_2] + 40, M[1,w])]

$[M[1,w] = 10, M[1,w-w_2] = 10\ \forall\ 4 \leq w \leq 10]$

weight capacity $\rightarrow$

weights

values

In this table, when the capacity is and the weight of the item is , we can’t choose the item. Therefore, the maximum knapsack value won’t update when capacity is equal to . For the rest of the capacity values, the maximum knapsack capacity values are updated by the formula.

Let’s continue the iteration and increase the value of . For the values $i = 3,\ w=1,\ w_i=1,\ v_i=20,\ w_i \leq w$ :

[M[3,1] = max(M[2,0] + 20, M[2,1]) = max(20,10) = 20]

Now, we need to increase the value of and run the loop $i = 3,\ w=(2, 3, 4)\ w_i=1,\ v_i=20,\ w_i \leq w$ :

[M[3,2] = max(M[2,1] + 20, M[2,2]) = max(10+20,40) = 40]

[M[3,3] = max(M[2,2] + 20, M[2,3]) = max(40+20,50) = 60]

[M[3,4] = max(M[2,3] + 20, M[2,4]) = max(50+20,50) = 70]

weight capacity $\rightarrow$

weights

values

Here, the weight = 1 . Therefore, we choose this item and update all the values in the row.

Let’s continue the iteration. Now, for the values $i = 4,\ w=1,\ w_i=3,\ v_i=20,\ w_i > w$ :

[M[4,1] = M[3,1] = 20]

Again, for the values $i = 4,\ w=(2, 3, 4, 5, 6, 7, 8, 9, 10)\ w_i=3,\ v_i=20,\ w_i \leq w$ :

[M[4,2] = M[3,2] = 40]

[M[4,3] = max(M[3,0] + 20, M[3,3]) = max(20,60) = 60]

[M[4,4] = max(M[3,1] + 20, M[3,4]) = max(20+20,70) = 70]

[M[4,5] = max(M[3,2] + 20, M[3,5]) = max(40+20,70) = 70]

[M[4,6] = max(M[3,3] + 20, M[3,6]) = max(60+20,70) = 80]

[M[4,7] = max(M[3,4] + 20, M[3,7]) = max(70+20,70) = 90]

[M[4,8] = max(M[3,5] + 20, M[3,8]) = max(70+20,70) = 90]

[M[4,9] = max(M[3,6] + 20, M[3,9]) = max(70+20,70) = 90]

[M[4,10] = max(M[3,7] + 20, M[3,10]) = max(70+20,70) = 90]

weight capacity $\rightarrow$

weights

values

The current weight here is . So, for the capacity values and , we can’t select this item. Hence, for capacity and , the maximum knapsack capacity values are unchanged. For the other capacity values, we do select the item and change the maximum capacity values.

It’s time to increase the value of and run the iteration. Therefore, the values in the loop $i = 5,\ w=1,\ w_i=5,\ v_i=60,\ w_i > w$ :

[M[5,1] = M[4,1] = 20]

We need to increase the value of , and everything else is unchanged. Hence, for $i = 5,\ w=(2, 3, 4, 5, 6, 7, 8, 9, 10)\ w_i=5,\ v_i=60,\ w_i > w$ :

[M[5,2] = M[4,2] = 40]

[M[5,3] = M[4,3] = 60]

[M[5,4] = M[4,4] = 70]

[M[5,5] = max(M[4,0] + 60, M[4,5]) = max(60,70) = 60]

[M[5,6] = max(M[4,1] + 60, M[4,6]) = max(20+60,80) = 80]

[M[5,7] = max(M[4,2] + 60, M[4,7]) = max(40+60,90) = 100]

[M[5,8] = max(M[4,3] + 60, M[4,8]) = max(60+60,90) = 120]

[M[5,9] = max(M[4,4] + 60, M[4,9]) = max(70+60,90) = 130]

[M[5,10] = max(M[4,5] + 60, M[4,10]) = max(70+60,90) = 130]

weight capacity $\rightarrow$

weights

values

100

120

130

Lastly, when the weight of the item is , we can update the values for which capacity value $\geq$ .

Finally, we’re done with the iterations. We end up with the result that when the weight limit is $\textbf{10}$ kgs, the maximum knapsack value is $\textbf{130}$ .

7. Time Complexity Analysis

Let’s analyze the time complexity of the dynamic programming algorithm in this section.

The first two initializations of function M[ ] can be done in $\mathcal{O}(1)$ time. The for loop that iterates from to takes $\mathcal{O}(n)$ time. Under this, there is another for loop which goes from to . It takes $\mathcal{O}(W)$ time. Finally, the max() can be computed in $\mathcal{O}(1)$ time.

Therefore, a 0-1 knapsack problem can be solved in $\mathcal{O}\mathbf{(nW)}$ using dynamic programming. It should be noted that the time complexity depends on the weight limit of .

Although it seems like it’s a polynomial-time algorithm in the number of items , as W increases from say 100 to 1,000 ( $\sim2^7$ to $\sim2^{10}$ ), processing goes from bits to bits. The time complexity increases exponentially with the number of bits.

For example, if the weight is not large, then the complexity can be perceived as polynomial time in the number of input items, hence the term “pseudo-polynomial”.

8. Conclusion

In this article, we’ve discussed the 0-1 knapsack problem in depth. We’ve explained why the 0-1 Knapsack Problem is NP-complete.

For solving this problem, we presented a dynamic programming-based algorithm. We ran the algorithm on an example problem to ensure the algorithm is giving correct results. Finally, we analyzed the time taken by the dynamic algorithm.

Persistence

REST

Security

1. Overview

2. General Definition

3. Variants of Knapsack Problem

3.1. 0-1 Knapsack Problem

3.2. Bounded Knapsack Problem

3.3. Unbounded Knapsack Problem

4. Why 0-1 Knapsack Problem Is NP-Complete?

5. Dynamic Programming Algorithm

6. An Example

7. Time Complexity Analysis

8. Conclusion