[Dynamic Programming 0-1 Knapsack Problem]

[Problem description]

0-1 knapsack problem: given n items and a knapsack. The weight of item i is w_i, its value is v_i, and the capacity of the backpack is c. How should I choose the items to put in the backpack so that the total value of the items in the backpack is maximized?

When choosing what to put in a backpack, there are only two choices for each item i, either to put it in the backpack or not to put it in the backpack. Item i cannot be loaded into the backpack multiple times, nor can only part of item i be loaded into the backpack. Therefore, this problem is called the 0-1 knapsack problem.

The formal description of this problem is, given c>0, w_i>0, v_i>0, 1 ≤ i ≤ n, it is required to find an n element 0-1 vector (x₁, x₂,…, x_n), x_i ∈ {0,1}, 1≤i

m

a

x

∑

i

=

1

n

v

i

?

x

i

max\sum_{i=1}^n{v~i~*x~i~}

maxi=1∑n?v i ?x i

∑

i

=

1

n

w

i

?

x

i

≤

c

\sum_{i=1}^n{w~i~*x~i~}≤c

i=1∑n?w i ?x i ≤c

x

i

∈

(

0

,

1

)

,

1

≤

i

≤

n

x~i~\in(0,1),1≤ i ≤ n

x i∈(0,1),1≤i≤n

[Algorithm Analysis]

1． Optimal substructure properties

The 0-1 knapsack problem has optimal substructure properties. Assume (y₁, y₂,…, y_n) is an optimal solution to the given 0-1 knapsack problem, Then (y2, y3, –·, yn) is an optimal solution to the corresponding sub-problem below:

m

a

x

∑

i

=

2

n

v

i

?

x

i

max\sum_{i=2}^n{v~i~*x~i~}

maxi=2∑n?v i ?x i

∑

i

=

2

n

w

i

?

x

i

≤

c

?

w

i

?

y

1

\sum_{i=2}^n{w~i~*x~i~}≤c-w~i~*y~1~

i=2∑n?w i ?x i ≤c?w i ?y 1

x

i

∈

(

0

,

1

)

,

2

≤

i

≤

n

x~i~\in(0,1),2≤ i ≤ n

x i∈(0,1),2≤i≤n
If not, suppose (z₂, z₃,…, z_n) is an optimal solution to the above sub-problem, And (y₂, y₃,··, y_n) is not its optimal solution. It can be seen from this that,

∑

i

=

2

n

v

i

?

z

i

>

∑

i

=

2

n

v

i

?

y

i

\sum_{i=2}^n{v~i~*z~i~}>\sum_{i=2}^n{v~i~*y~i~}

i=2∑n?v i ?z i >i=2∑n?v i ?y i , and

w

1

?

y

1

+

∑

i

=

2

n

w

i

?

z

i

≤

c

w~1~*y~1~ + \sum_{i=2}^n{w~i~*z~i~}≤c

w 1 ?y 1 + i=2∑n?w i ?z i ≤c. therefore,

v

1

?

y

1

+

∑

i

=

2

n

v

i

?

z

i

>

∑

i

=

1

n

v

i

?

y

i

v~1~*y~1~ + \sum_{i=2}^n{v~i~*z~i~}>\sum_{i=1}^n{v~i~*y~i~ }

v 1 ?y 1 + i=2∑n?v i ?z i >i=1∑n?v i ?y i

w

1

?

y

1

+

∑

i

=

2

n

w

i

?

z

i

≤

c

w~1~*y~1~ + \sum_{i=2}^n{w~i~*z~i~}≤c

w 1 ?y 1 + i=2∑n?w i ?z i ≤c
This shows that (y₁, z₂,···,z_n) is a better solution to the given 0-1 knapsack problem , thus (y₁, y₂,…, y_n) is not the optimal solution to the given 0-1 knapsack problem. This is a contradiction.

2． Recursive relationship

Let the subproblem of the 0-1 knapsack problem be given

m

a

x

∑

k

=

i

n

v

k

?

x

k

max\sum_{k=i}^n{v~k~ * x~k~}

maxk=i∑n?v k ?x k

m

a

x

∑

k

=

i

n

w

k

?

x

k

≤

j

max\sum_{k=i}^n{w~k~ * x~k~}≤j

maxk=i∑n?w k ?x k ≤j

x

k

∈

(

0

,

1

)

,

i

≤

k

≤

n

x~k~\in(0,1),i≤ k ≤ n

x k∈(0,1),i≤k≤n
The optimal value of is m(i,j), that is, m(i,j) is the optimal value of the 0-1 knapsack problem when the backpack capacity is j and the optional items are i, i+1,…,n. Based on the optimal substructure properties of the 0-1 knapsack problem, the recursive formula for calculating m(i, j) can be established as follows:

m

(

i

,

j

)

=

{

m

a

x

{

m

(

i

+

1

,

j

)

,

m

(

i

+

1

,

j

?

w

i

)

+

v

i

}

j

≥

w

i

m

(

i

+

1

,

j

)

0

≤

j

≤

w

i

m(i, j)=\left\{ \begin{array}{rcl} max\lbrace m(i + 1, j),m(i + 1, j-w~i~) + v~i~\rbrace & amp; & amp; { j≥w~i~}\ m(i + 1, j) & amp; & amp; {0≤j≤w~i~} \end{array} \right.

m(i, j)={max{m(i + 1, j),m(i + 1, j?wi ) + v i }m(i + 1, j)j≥w i 0≤j≤w i ?

m

(

n

,

j

)

=

{

v

n

j

≥

w

n

0

0

≤

j

≤

w

n

m(n, j)=\left\{ \begin{array}{rcl} v~n~ & amp; & amp; { j≥w~n~}\ 0 & amp; & amp; {0≤j ≤w~n~} \end{array} \right.

m(n,j)={v n 0j≥w n 0≤j≤w n ?

3. Algorithm description

Based on the above discussion, when w_i(1≤i≤n) is a positive integer, a two-dimensional array m[ ][ ] is used to store the corresponding value of m(i, j), and the solution can be designed The dynamic programming algorithm Knapsack for the 0-1 knapsack problem (see [C++ code implementation] for specific implementation).
After calculation according to the above algorithm Knapsack, m[1][c] gives the required optimal value of the 0-1 knapsack problem. The corresponding optimal solution can be calculated by the algorithm Traceback as follows. If m[1 ][ c]=m[ 2][c ], then x₁=0, otherwise x₁=1, when x_{1< When /sub>=0, continue to construct the optimal solution from mm[2][c]. When x1=1, continue to construct the optimal solution from m[ 2][c -w1]. By analogy, the corresponding optimal solution (x1, x2,…, xn) can be constructed.}

[C++ code implementation]

//Dynamic programming algorithm for solving 0-1 knapsack problem
template<class Type>
void Knapsack(Type v, int w, int c, int n, Type** m)
{<!-- -->
int jMax = min(w[n] - 1, c);
for (int j = 0; j <= jMax; j + + )m[n][j] = 0;
for (int j = w[n]; j <= c; j + + )m[n][j] = v[n];
for (int i = n - 1; i > 1; i--) {<!-- -->
jMax = min(w[i] - 1, c);
for (int j = 0; j <= jMax; j + + )m[i][j] = m[i + 1][j];
for (int j = w[i]; j <= c; j + + )m[i][j] = max(m[i + 1][j], m[i + 1][j - w[ i]] + v[i]);
}
m[1][c] = m[2][c];
if (c >= w[1])m[1][c] = max(m[1][c], m[2][c - w[1]] + v[1]);
}
//Construct the optimal solution
template<class Type>
void Traceback(Type** m, int w, int c, int n, int x)
{<!-- -->
for (int i = 1; i < n; i + + )
if (m[i][c] == m[i + 1][c])x[i] = 0;
else {<!-- --> x[i] = 1; c -= w[i]; }
x[n] = (m[n][c]) ? 1 : 0;
}