背包问题
贪心算法
在第一次遇到背包问题的时候，我相信很多人的想法和我一样，就是使用贪心算法，我们只需要算出每件物品的性价比，也就是物品权重（价值/重量），然后排序，从高向低选做局部最优解，由此得出整体最优解，求出最大价值。
这种方法对于可拆分背包当然可以，但是对于01背包，貌似就没那么简单了。
举个例子：求 $N~=~3,~V~=~15,~v~=~[~6,~7,~10~],~w~=~[~8,9,15~]$ 时的最优解，如果使用贪心那么得出来的答案会是 $w~[~2~]~=~15$，显然答案是错误的，应该是 $w~[~0~]~+~w~[~1~]~=~17$。那为什么呢？
因为对于贪心算法，他只关注性价比，忽视了背包的空间，在空间上的浪费就会增加，导致单位体积物品的价值降低了，最后反而并不是整体最优解。
对于这种问题，我们使用动态规划算法来解决（当然暴力枚举也可以，这里不考虑），动态规划与贪心算法其实很相似，他们唯一的不同在于：贪心每次只做一个局部最优决策，每往下的决策越少；而动态规划则是重叠子问题，将原始问题分成若干个相关子问题。虽然都是通过获得每一个最优子结构来获得整体最优。但是这么对比起来，贪心是不是就显得有点鼠目寸光了。而动态规划则是统筹全局呢。
动态规划
那么现在我们来学习动态规划的使用，首先我们要知道，既然叫动态规划，那么他一定是动态的，同时他的每个状态依赖于前一次的状态。为了方便描述这种状态，现在我们可以给他一个二维表：dp[N][V]
状态：dp[i][j] 表示选择前 i 个物品，体积为 j 时的最优方案
状态转移方程：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) (_当作递推公式看就行了_)
dp[i - 1][j]：上一个状态体积为 j 的价值
dp[i - 1][j - v[i]] + w[i]：上一状态体积为 {j - v[i] (第 i 件物品体积)}的价值 + w[i]（第 i 件物品的价值）
这样我们就可以看到每个状态下各种体积的最优解。
$01$背包
问题描述
有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。
第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
数据范围
$0<N,V≤1000$
$0<v_i,w_i≤1000$
算法：动态规划二维表
时间和空间复杂度： $~O(n·m)$
现在我们用上述方法解决 $01$背包问题。
核心代码
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 延续上一状态
dp[i][j] = dp[i-1][j];
if (j >= v[i])
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]); // 状态转移
}
}
好了，这样就可以解决 $01$ 背包的简单问题了。
不过，到这里还没有结束，如果真的理解了动态规划，那么应该很容易发现，上述代码是可以优化的。
我们每多一个物品做状态转移，只需要上一次的全部状态，并不需要之前所有状态；所以我们可以将二维表转化为一维表来节省空间的使用。空间复杂度降到$~O(m)$
注意，这里的j循环是从高位到低位，因为dp[j-v[i]]表示的是容量为j-v[i]的背包装前i-1个物品的最大价值。物品容量i最大价值循环，从高位到低位同一物品至多拿一次；反之，则会出现多次。
算法：动态规划一维表
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define N 1007
int n, m, v, w, dp[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v >> w;
for (int j = m; j >= v; j--) {
dp[j] = max(dp[j], dp[j-v] + w);
}
}
cout << dp[m];
return 0;
}
现在 $01$ 背包问题结束了，我们来看完全背包问题。
完全背包
完全背包是在 $01$ 背包的基础上将每种物品数量变为 $∞$ 大，而不是只能取一个了。
思路调整
还记得我们之前 $01$ 背包的状态转移方程吗？
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])
现在我们对他进行延申。
dp[i][j] = max(dp[i - 1][j - k * v[i]] + k * w[i]) (k = 0, 1, ··· , n)
dp[i][j - v[i]] = max(dp[i - 1][j - k * v[i]] + k * w[i]) (k = 1, 2, ··· , n)
将上述两式相减就可以得出完全背包的状态转移方程了。
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
同 $01$ 背包一样，我们将二维表进行优化得出代码：
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define N 1007
int n, m, v, w, dp[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v >> w;
for (int j = v; j <= m; j++) {
dp[j] = max(dp[j], dp[j-v] + w);
}
}
cout << dp[m];
return 0;
}
注意这里完全背包与 $01$ 背包的的区别！！！我们现在将两个方程放在一起，并对核心代码进行比较。
状态转移方程
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) // 01背包
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]) // 完全背包
核心代码
// 01背包
for (int i = 1; i <= n; i++)
for (int j = m; j <= v[i]; j++) // 从高位到低位
dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
// 完全背包
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <= m; j++) // 从低位到高位
dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
还记得之前二维表优化为一维表的方法吗？在这里我们也可以这样理解，dp[j-v[i]]表示的是容量为j-v[i]的背包装前i-1个物品的最大价值。物品容量i最大价值循环，从高位到低位同一物品至多出现一次，而从低位到高位则同一物品可以出现多次。
学完 $01$ 背包和完全背包，趁着脑子还热，我们继续来学习一下多重背包问题吧！！！先来看看问题描述。
多重背包问题 I
问题描述
有 $N$ 件物品和一个容量是 $V$ 的背包。
第 $i$ 件物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
数据范围
$0<N,V≤100$
$0<v_i,w_i,s_i≤100$
算法：动态规划 + 暴力
时间复杂度： $~O(m·n·s)$
我们先来看一下多重背包问题的状态转移方程，用 $k$ 表示每个物品选中次数，
f[i][j] = max(f[i - 1][j - k * v[i]] + k * w[i]) (k = 0, 1, ···, s[i])
想要得到最终价值并不难，我们只要在 $01$ 背包的 $j$ 循环下加个 $k$ 循环，循环给出两个条件：
$1)~k~≤~s$
$2)~k~*~v~≤~j$
这样就可以得出最大价值了。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define N 107
int n, m, v, w, s, dp[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v >> w >> s;
for (int j = m; j >= v; j--) {
for (int k = 1; k <= s && k * v <= j; k++) {
dp[j] = max(dp[j], dp[j - k * v] + k * w);
}
}
}
cout << dp[m];
return 0;
}
这样就结束了吗？并没有，如果我们将范围扩大到：$0<N≤1000$，$0<V≤2000$,$0<v_i,w_i,s_i≤2000$ 会怎么样呢？显然 $n·m·s~＞~10^9$，这样提交一定是会 $TLE$ 的。那么我们该怎么优化呢？
多重背包问题 II
数据范围变为：
$0<N≤1000$
$0<V≤2000$
$0<v_i,w_i,s_i≤2000$
算法：动态规划 + 二进制
时间复杂度： $~O(m·n·logs)$
原来的做法是，对于每件物品，我们一次拿一个。现在我们把每种物品的总件数 $s$，分成一个又一个堆，我们每次都拿其中的一个堆，那么我们该怎么样分配呢？
我们可以利用二进制的性质对其进行优化，比如我们现在有 $7$ 件物品，原来我们最多可能要拿 $7$次，现在我们使用二进制换算 $7B~=~111$，我们可以把他拆解成 $100~010~001$ 这三个堆，他们可以组合成任意 $≤7$ 的数，而且每种组合都会得到不同的数，那么我至多只需要拿 $3$ 次就可以拿完。
假设我要拿 $6$ 件，原来我们一个一个拿，需要拿 $6$ 次才能全部取完。现在我只需要拿 $2$ 次，我们只要拿 $~2,~4$ 这两堆就可以了。这样就可以将时间复杂度 $~O(m·n·s)$ 降到了 $~O(m·n·logs)$，大概从 $4·10^9$ 降到了 $2·10^7$，可以通过。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define N 2007
#define M 12007
// 多重背包问题
// 二进制优化
int n, m, vi, wi, si, k, ans;
int w[M], v[M], dp[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> vi >> wi >> si;
// 进行二进制拆解，每次左移一位
for (int k = 1; k <= si; k <<= 1) {
w[++ans] = wi * k; // 这一位的全部价值
v[ans] = vi * k; // 这一位的全部体积
si -= k; // 减去这一位的全部
}
// 最后一位放剩余部分
if (si > 0) {
w[++ans] = wi * si;
v[ans] = vi * si;
}
}
// 因为已经进行了二进制优化，所以此时 n 变为 ans
for (int i = 1; i <= ans; i++) {
for (int j = m; j >= v[i]; j--) {
dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
}
}
cout << dp[m];
return 0;
}
思考？
在 $01$ 背包中我们对【空间】进行了优化，空间复杂度从 $~O(n·m)$ 降到了 $~O(m)$；
在多重背包中我们利用二进制思想
对同种【物品的分类】进行了优化，时间复杂度从 $~O(m·n·s)$ 降到了 $~O(m·n·logs)$；
到此已经是最优了吗？我们还可以对哪些部分进行优化？
