0/1背包问题可以形式化表述为一个整数规划问题：
m
a
x
∑
i
=
1
n
v
i
x
i
{
∑
i
=
1
n
w
i
x
i
≤
c
x
i
∈
{
0
,
1
}
1
≤
i
≤
n
max\sum_{i=1}^n{v_ix_i} \ \ \ \ \ {∑ni=1wixi≤cxi∈{0,1}1≤i≤n
问题的解为一个n元0-1向量，
(
x
1
,
x
2
,
x
3
,
.
.
.
,
x
n
)
,
x
i
∈
{
0
,
1
}
(
1
≤
i
≤
n
)
(x_1,x_2,x_3,...,x_n),\ x_i \in \{0,1\} \ (1 \leq i \leq n)
(x1,x2,x3,...,xn), xi∈{0,1} (1≤i≤n)。0/1背包问题具有最优子结构性质，因此可以使用动态规划方法解决。最优子结构性质证明如下：
首先假设原问题的一个最优解为
(
x
1
,
x
2
,
x
3
,
.
.
.
,
x
n
)
(x_1,x_2,x_3,...,x_n)
(x1,x2,x3,...,xn)，考虑0/1背包的一个子问题为：
m
a
x
∑
i
=
1
n
−
1
v
i
x
i
{
∑
i
=
1
n
−
1
w
i
x
i
≤
c
−
w
n
x
n
x
i
∈
{
0
,
1
}
1
≤
i
≤
n
−
1
max\sum_{i=1}^{n-1}{v_ix_i} \ \ \ \ \ {∑n−1i=1wixi≤c−wnxnxi∈{0,1}1≤i≤n−1
则相应的子问题的最优解应该为
(
x
1
,
x
2
,
x
3
,
.
.
.
,
x
n
−
1
)
(x_1,x_2,x_3,...,x_{n-1})
(x1,x2,x3,...,xn−1)。假设存在一个解
(
x
1
′
,
x
2
′
,
x
3
′
,
.
.
.
,
x
n
−
1
′
)
(x'_1,x'_2,x'_3,...,x'_{n-1})
(x1′,x2′,x3′,...,xn−1′)，使
∑
i
=
1
n
−
1
v
i
x
i
′
>
∑
i
=
1
n
−
1
v
i
x
i
\sum_{i=1}^{n-1}{v_ix'_i}>\sum_{i=1}^{n-1}{v_ix_i}
∑i=1n−1vixi′>∑i=1n−1vixi，由于
∑
i
=
1
n
−
1
w
i
x
i
≤
c
−
w
n
x
n
\sum_{i=1}^{n-1}{w_ix_i}\leq c-w_nx_n
∑i=1n−1wixi≤c−wnxn，可得
∑
i
=
1
n
−
1
w
i
x
i
+
w
n
x
n
≤
c
\sum_{i=1}^{n-1}{w_ix_i}+w_nx_n\leq c
∑i=1n−1wixi+wnxn≤c，即存在一个n元0-1向量
(
x
1
′
,
x
2
′
,
x
3
′
,
.
.
.
,
x
n
−
1
′
,
x
n
)
(x'_1,x'_2,x'_3,...,x'_{n-1},x_n)
(x1′,x2′,x3′,...,xn−1′,xn)是原问题的一个可行解。可以得到：
∑
i
=
1
n
−
1
v
i
x
i
′
+
v
i
x
n
>
∑
i
=
1
n
−
1
v
i
x
i
+
v
i
x
n
=
∑
i
=
1
n
v
i
x
i
\sum_{i=1}^{n-1}{v_ix'_i}+v_ix_n>\sum_{i=1}^{n-1}{v_ix_i}+v_ix_n=\sum_{i=1}^n{v_ix_i}
i=1∑n−1vixi′+vixn>i=1∑n−1vixi+vixn=i=1∑nvixi
即这个可行解计算的结果比原问题的最优解要大，这产生了矛盾。因此可以证明0/1背包问题具有最优子结构性质。
设0/1背包问题的子问题为：
m
a
x
∑
k
=
1
i
v
k
x
k
{
∑
k
=
1
i
w
k
x
k
≤
j
x
k
∈
{
0
,
1
}
1
≤
k
≤
i
max\sum_{k=1}^i{v_kx_k} \ \ \ \ \ {∑ik=1wkxk≤jxk∈{0,1}1≤k≤i
最优解用m(i,j)表示，i表示可选物品1-i，j表示容量为j。根据0/1背包的最优子结构性质，可以得到计算m(i,j)的递归式如下：
i
=
1
m
(
i
,
j
)
=
{
0
0
≤
j
<
w
i
v
i
w
i
≤
j
i
>
1
m
(
i
,
j
)
=
{
m
(
i
−
1
,
j
)
0
≤
j
<
w
i
m
a
x
{
m
(
i
−
1
,
j
)
,
m
(
i
−
1
,
j
−
w
i
)
+
v
i
}
w
i
≤
j
i = 1 \ \ \ \ m(i,j)= {00≤j<wiviwi≤j
根据以上构造的递推关系，进行最优值的计算。
int solution(int m[][c+1],int weight[],int value[],int c,int n){
//初始化，当j>=weight[0]，m[0][j]=value[0]
memset(dp,0,sizeof(dp));
for(int j=weight[0];j<=c;j++) m[0][j]=value[0];
for(int i=1;i 主要的计算量为m[i][j]的计算，因此该算法的时间复杂度为 O ( c n ) O(cn) O(cn)。
根据m[i][j]中记录的信息判断最优解是从哪个子问题产生的，得到结果的0-1向量：
void traceback(int m[][c+1], int weight[] ,int n, int c, int x[]){
for(int i=1;i