0/1背包问题

背包问题(Knapsack Problem)是一类经典的动态规划问题，是一种组合优化的NP完全(NP-Complete, NPC)问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，如何选择，才能使得物品的总价值最高。NPC问题是没有多项式时间复杂度的解法的，但利用动态规划，可以在伪多项式时间复杂度下求解背包问题。本文讨论的是背包问题中的最基本的0/1背包问题。

问题描述

一共有N件物品，第i件物品的重量是w[i],价值是v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？

分析

如果采用暴力法，对于每件物品都有两种状态取或不取，时间复杂度为O(2^N)，这是不可接受的。如果采用动态规划，则可以将复杂度降为O(N·W)。

我们的目标是背包内物品的总价值，而变量是物品和背包的当前重量，因此我们可以设状态dp：dp[i][j]表示考虑前i件物品且背包当前重量为j时的背包物品总价值。

那么，对于dp[0][0...W]初始化为0，表明考虑前0个物品后，背包物品总价值为0。当i>0时，dp[i][j]会有两种情况：

1. 不装入第i件物品，则dp[i][j] = dp[i-1][j]。
2. 装入第i件物品，则dp[i][j] = dp[i-1][j - w[i]] + v[i]。

此时，我们可以得到状态转移方程(j>=w[i])：dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])。

我们发现，dp[i][j]只和dp[i-1][0...j-1]有关，所以我们可以采用动态规划常用的方法“滚动数组”对空间进行优化，即去掉dp的第一维。需要注意的是，为了防止上一层循环的状态dp被覆盖，循环的时候 j 只能从尾部开始枚举。于是有了如下代码：

int dp[W] = {0};
for(int i = 1;i<=N;i++){
    for(int j = W-1;j>=w[i]-1;j--){
        dp[j] = max(dp[j], dp[j−w[i]]+v[i]);
    }
}

总结

利用动态规划解决0/1背包问题，时间复杂度为O(N·W), 空间复杂度为O(W)。由于W的值是W的位数的幂，所以这个时间复杂度是伪多项式时间。

动态规划的核心思想避免重复计算在01背包问题中体现得淋漓尽致。第i件物品装入或者不装入而获得的最大价值完全可以由前面i-1件物品的最大价值决定，暴力枚举忽略了这个事实。