01背包通俗版讲解

01背包是一种非常经典的动态规划问题，这里对01背包问题进行详细解读。

01背包问题题目描述

有 \(N\) 件物品和一个容量为 \(V\) 的背包。第\(i\)件物品的体积是 \(c[i]\) ，价值是 \(w[i]\) ，求将哪些物品装入背包可使价值总和最大。
01背包问题解析
对于所有的动态规划问题，第一步都是确定状态。我们定义状态 \(dp[i][j]\) 是表示目前正在枚举第 \(i\) 个物品，目前已取的总体积为 \(j\)，最大价值为\(dp[i][j]\)。
第二步自然是找状态转移方程。
首先我们注意一点：物品只有取和不取两种选择，这是符合我们日常生活的。状态转移方程就需要从这里为突破口来思考：
(1)：假如我们不取这个物品，那么 \(dp[i][j]\) 肯定是能从上一个物品，同样体积转移过来的，所以 \(dp[i][j]=dp[i?1][j]\)。
(2)：假如我们取这个物品,那么 \(dp[i][j]\) 是从什么情况转移呢？思考一下，首先可以得出， \(dp[i][j]\) 肯定可以从上一个物品转移过来，那可以从什么体积转移呢？我们注意到，对于 \(dp[i][j]\) ，它的当前取到的体积为 \(j\)，由于我们取了这个物品，所以上一个物品的体积为 j?c[i]j?c[i] j - c[i]j?c[i]。所以我们可以得出， \(dp[i][j]\) 可以从 \(dp[i - 1][j - c[i]]\) 转移过来，由于我们取了这个物品，所以还要加上这个物品的价值 w[i]w[i] w[i]w[i] 。
所以我们可以得出01背包的状态转移方程（很重要，尽量背下来！！）
\(j>=c[i]\) 时，\(dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i])\)
\(j < c[i]\) 时，\(dp[i][j] = dp[i - 1][j]\)。

上代码：

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

int dp[21][1010];
int w[21], c[21];
int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> c[i];
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= V; j++) {
            if (j >= c[i]) {
                dp[i][j] = max(dp[i - 1][j - c[i]] + w[i], dp[i - 1][j]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout << dp[N][V] << endl;
    return 0;
}

01背包滚动数组空间优化

我们分析一下空间复杂度：\(O(NV)\)，显然较大，我们要优化一下，用什么优化呢？

我们可以用滚动数组！
观察转移方程，易得 \(dp[i][j]\) 只从 \(dp[i - 1][j]\) 和 \(dp[i - 1][j - c[i]]\) 转移，所以可以用一个\(flag\) 代替 \(i\) ，用 \(1 - flag\) 代替 \(i - 1\)。
这样只需要定义 \(dp[2][maxn]\) ,大大节省了空间。

上代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int dp[2][1010];
int w[21], c[21];

int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> c[i];
    }
    int flag = 1;
    for (int i = 1; i <= N; i++) {
        for(int j = 0;j <= V; j++) {
            if(j >= c[i]) {
                dp[flag][j] = max(dp[1 - flag][j - c[i]] + w[i], dp[1 - flag][j]);
	    } else {
                dp[flag][j] = dp[1 - flag][j];
	    }
	}
        flag = 1 - flag;
    }
    cout << dp[1 - flag][V] << endl;
    return 0;
}

01背包空间优化

这里给大家介绍真正的空间优化。
如果我们将 \(dp\) 数组只用来表示体积，那么我们可以让内层循环的 \(j\) 从 \(V\) 到 \(0\) 枚举，那么当前状态转移方程的 \(dp[j]\) 和 \(dp[j - c[i]]\) 由于我们没有更新，所以仍然是计算上一轮 \(i - 1\) 个物品的，就是二维状态下的 \(dp[1 - flag][j]\) 和 \(dp[i - flag][j - c[i]]\)。所以现在我们的转移方程是：
\(dp[j] = max(dp[j], dp[j - c[i]] + w[i])\)

上代码：

#include <iostream>
#include <cstring>
using namespace std;

int dp[1010];
int w[21], c[21];

int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> c[i];
    }
    for (int i = 1; i <= N; i++) {
	for (int j = V; j >= c[i]; j--) {
             dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
	}
    }
    cout << dp[V] << endl;
    return 0;
}

END

01背包通俗版讲解

原文：https://www.cnblogs.com/LovelyPanda/p/12562819.html