所谓 01 背包问题，就是给定 n 种物品，每种物品都有重量 wi 和价值 vi，每种物品都只有一个。另外，背包容量为 W。求解在不超过背包容量的前提下将哪些物品装入背包，才可以使背包内的物品价值之和最大。每种物品只有一个，要么不装，要么装。

假设第 i 阶段处理第 i 种物品，第 i-1 阶段处理第 i-1 种物品，则当处理第 i 种物品时，前 i-1 种物品已处理完毕，只需考虑第 i-1 阶段向第 i 阶段的转移。

用 c

表示将前 i 种物品装入容量为 j 的背包可以获得的最大价值。第 i 种物品的处理状态包括以下两种：

若背包容量不足，则肯定不可以装入，价值仍为前 i-1 种物品处理后的结果；若背包容量充足，则考查装入不装入此物品哪种使得背包内的物品价值之和最大。

状态转移方程：

算法步骤 1) 初始化初始化数组 c

第 0 行第 0 列为 0：c

=0，c

=0，其中 i=0，1，2，…，n，j=0，1，2，…，W，表示装入第 0 种物品或背包容量为 0 时获得的价值均为 0。

2) 循环阶段 3) 构造最优解c

就是在不超过背包容量时可以装入物品的最大价值（最优值）。若还想知道具体装入了哪些物品，则需要根据数组 c

逆向构造最优解。

可以用一维数组 x

存储解向量，x

=1 表示第 i 种物品被装入背包，x

=0 表示第 i 种物品未被装入背包：

初始时 i=n，j=W。 若 c

>c

i-1

，则说明第 i 种物品被装入背包，令 x

=1，j-=w

；若 c

≤c

i-1

，则说明第i种物品没被装入背包，令 x

=0。 i–，转向第 2 步，直到 i=1 时处理完毕。

此时已经得到解向量（x

，x

，…，x

），直接输出该解向量，也可以仅输出 x

=1 的物品序号 i。

完美图解有 5 种物品，重量分别为 2、5、4、2、3，价值分别为 6、3、5、4、6。背包容量为 10。求解在不超过背包容量的前提下将哪些物品装入背包，才可以使背包内的物品价值之和最大。

1) 初始化。c

表示将前 i 种物品装入容量为 j 的背包可以获得的最大价值。初始化数组 c

第 0 行第 0 列为 0。

2) 按照状态转移方程处理第 1 种物品（i=1），w

=2，v

=6，如下图所示。

其中：

3) 按照状态转移方程处理第 2 种物品（i=2），w

=5，v

=3，如下图所示。

其中：

4) 按照状态转移方程处理第 3 种物品（i=3），w

=4，v

=5，如下图所示。

其中：

5) 按照状态转移方程处理第 4 种物品（i=4），w

=2，v

=4，如下图所示。

其中：

6) 按照状态转移方程处理第 5 种物品（i=5），w

=3，v

=6，如下图所示。

其中：

7) 构造最优解：

算法实现 1) 求解装入背包的物品的最大价值c

表示将前 i 种物品装入容量为 j 的背包可以获得的最大价值。对每种物品都进行计算，背包容量 j 为 1~W：

算法代码：

for(int i=1;i<=n;i++) //计算 c[i][j]
    for(int j=1;j<=W;j++)
        if(j<w[i]) //若物品的重量大于背包容量，则不装入此物品
            c[i][j]=c[i-1][j];
        else //否则比较装入与不装入此物品哪种使得背包内的物品价值之和最大
            c[i][j]=max(c[i-1][j],c[i-1][j-w[i]]+v[i]);
cout<<"装入背包的最大价值为:"<<c[n][W]<<endl;

2) 最优解构造根据数组 c

的计算结果逆向递推最优解，若 c

>c

i-1

，则说明第 i 种物品被装入背包，令 x

=1，j-=w

；若 c

≤c

i-1

，则说明第 i 种物品没被装入背包，令 x

=0。

算法代码：

int j=W; //逆向构造最优解
for(int i=n;i>0;i--) {
    if(c[i][j]>c[i-1][j]) {
        x[i]=1;
        j-=w[i];
    }
    else
        x[i]=0;
}
cout<<"装入背包的物品序号为：";
for(int i=1;i<=n;i++)
    if(x[i]==1)
        cout<<i<<" ";

本算法使用了两层 for 循环，时间复杂度为 O(nW)；使用了二维数组 c

，空间复杂度为 O(nW)。

算法优化根据求解过程可以看出，依次处理 1..n 的物品，当处理第 i 种物品时，只需第 i-1 种物品的处理结果，若不需要构造最优解，则装入第 i-1 种物品之前的处理结果已经没用了。

例如，处理到第 4 种物品（w

=2，v

=4）时，只需第 3 种物品的处理结果（上一行）。求第 j 列时，若 j

既然只需上一行当前列和前面列的值，则只用一个一维数组倒推就可以了：

例如，处理到第 4 种物品（w

=2，v

=4）时，倒推的计算过程如下图所示。

为什么不正推呢？下面进行推理。

正推的情况：

第 i 阶段表示在处理第 i 种物品时，前 i-1 种物品已被处理完毕。倒推时，从后往前推，前面的值还未更新，仍为第 i-1 阶段的结果，这意味着总是用第 i-1 阶段的结果更新第 i 阶段，即从第 i-1 阶段向第 i 阶段进行状态转移。第 i-1 阶段的结果不包括第 i 种物品，保证第 i 种物品最多只被装入背包 1 次，如下图所示。

正推时，从前向后推，前面的值已被更新为第 i 阶段，这意味着用第 i 阶段的结果更新第 i 阶段，即从第 i 阶段向第 i 阶段进行状态转移。第 i 种物品可能被装入背包多次，如下图所示。

在 01 背包问题中，因为每种物品只有一个且最多被装入 1 次，所以必须通过倒推求解。若每种物品有多个且可被装入多次（完全背包），则可通过正推求解。

算法代码：

void opt2(int n,int W) { // 01 背包问题，一维数组优化
    for(i=1;i=w[i];j--) //逆序循环（倒推）
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}

本算法包含两层 for 循环，时间复杂度为 O(nW)；使用了一维数组 dp

，空间复杂度为 O(W)。