【算法笔记】动态规划基础（二）：背包dp

01背包

例题

2. 01背包问题

状态表示

分析问题，首先需要遍历每一个物品，题中要求最大价值，限制条件是最大体积，要遍历所有可能的体积，因此要开两维：$dp[i][j]$

• 集合：所有从前$i$个物品中选，所选物品总体积不超过$j$的方案
• 属性：（所选物品总价值的）最大值

综上：$dp[i][j]$表示所有从前$i$个物品中选，所选物品总体积不超过$j$的最大价值。

状态计算

集合划分：将这个集合划分成几个不同的集合，就要找一个不同的步骤。

最后一步就不同，有点$dfs$指数级枚举的感觉，第$i$个物品可以选、也可以不选。

如果不选第$i$个物品，跟看第$i$个物品前相比，总体积不变、总价值不变，也就是$dp[i-1][j]$
如果选第$i$个物品，跟看第$i$个物品前相比，体积增加了$v[i]$，价值增加了$w[i]$，当前的总体积不超过$j$，那选之前的体积就不超过$j-v[i]$，也就是$dp[i-1][j-v[i]]+w[i]$，这里可以看出，要保证$j-v[i]\ge 0$，也就是$j\ge v[i]$（选的物品总体积不能超过$j$，$j$还小于$v[i]$， 那第$i$个物品当然不能选了…）

可以得到状态转移方程：
$dp[i][j]=max(dp[i][j],dp[i-1][j])$
$dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i])(j\ge v[i])$

初始化

求最大价值，并且总价值也是从0开始加的，直接将所有位置初始化成0即可。

AC代码

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;int dp[N][N];
int v[N], w[N];int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> v[i] >> w[i];}for(int i = 1; i <= n; i++){for(int j = 0; 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]);} }cout << dp[n][m] << endl;return 0;
}

完全背包

例题

3. 完全背包问题

状态表示

和01背包分析方式相同，唯一不同的是，这次每一个物品可以选任意次，如果从$dfs$的角度想，就是把选和不选的两种状态变成了选多少个，就是加了一层$for$循环，$dp$也是一样的道理。还是两维，
和01背包相同：

$dp[i][j]$表示所有从前$i$个物品中选，所选物品总体积不超过$j$的最大价值。

状态计算

多了一重$for$循环遍历每个物品选多少个，在01背包选的基础上，选多少个也就是减多少个$v[i]$、加多少个$w[i]$，状态转移方程也就有了。

$$dp[i][j]=\underset{0\le k\le t}{\max }(dp[i][j],dp[i-1][j-k\cdot v[i]]+k\cdot w[i]),t=\lfloor \frac{j}{v[i]}\rfloor$$

初始化

求最大价值，并且总价值也是从0开始加的，直接将所有位置初始化成0即可。

TLE代码

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;int dp[N][N];
int v[N], w[N];int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){for(int k = 0; k * v[i] <= j; k++){dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);}}}cout << dp[n][m] << endl;return 0;
}

多重背包

例题

4. 多重背包问题 I

状态表示

和完全背包相同，就是加了个限制：第$i$个物品选的数量不能超过$s[i]$，就是第3重$for$循环&&上这个限制即可，其他都相同：

$dp[i][j]$表示所有从前$i$个物品中选，所选物品总体积不超过$j$的最大价值。

状态计算

$$dp[i][j]=\underset{0\le k\le t，k\le s[i]}{\max }(dp[i][j],dp[i-1][j-k\cdot v[i]]+k\cdot w[i]),t=\lfloor \frac{j}{v[i]}\rfloor$$

初始化

求最大价值，并且总价值也是从0开始加的，直接将所有位置初始化成0即可。

AC代码

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 105;int dp[N][N];
int v[N], w[N], s[N];int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> v[i] >> w[i] >> s[i];}for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){for(int k = 0; k <= s[i] && k * v[i] <= j; k++){dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);}}}cout << dp[n][m] << endl;return 0;
}

分组背包

例题

9. 分组背包问题

状态表示

分组背包问题是每组中有若干物品，每组只能不选或从中选一个，那是不是可以将01背包的第一重$for$循环遍历每个物品变成遍历每组物品，再一重$for$循环遍历一下组中的所有物品，看选哪个，剩下的就和01背包完全相同了。

$dp[i][j]$表示所有从前$i$组物品中选，所选物品总体积不超过$j$的最大价值。

状态计算

$$dp[i][j]=\max (dp[i-1][j],\underset{1\le k\le s[i]}{\max }(dp[i-1][j-w[i][k]]+v[i][k]))$$

初始化

求最大价值，并且总价值也是从0开始加的，直接将所有位置初始化成0即可。

AC代码

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 105;int s[N], v[N][N], w[N][N];
int dp[N][N];int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> s[i];for(int j = 1; j <= s[i]; j++){cin >> v[i][j] >> w[i][j];}}for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){dp[i][j] = max(dp[i][j], dp[i - 1][j]);for(int k = 1; k <= s[i]; k++){if(j >= v[i][k]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i][k]] + w[i][k]);}}}cout << dp[n][m] << endl;return 0;
}

二维费用背包

例题

8. 二维费用的背包问题

状态表示

二维费用背包就是在标准的01背包的基础上，又加了一层限制，怎么对待体积限制的就怎么对待重量限制，就是多了一重$for$循环遍历所有可能的重量，数组也对应加了一维，因此要开三维：$dp[i][j][k]$

• 集合：所有从前$i$个物品中选，所选物品总体积不超过$j$且总重量不超过$k$的方案
• 属性：（所选物品总价值的）最大值

综上：$dp[i][j][k]$表示所有从前$i$个物品中选，所选物品总体积不超过$j$且总重量不超过$k$的最大价值。

状态计算

其他和01背包相同，也是看选不选第$i$个物品，不选的话总体积、总重量、总价值都不变，选的话总体积在原来的基础上增加$v[i]$，那选之前的最大体积就应该是$j-v[i]$，总重量在原来的基础上增加$m[i]$，那选之前的最大体积就应该是$k-m[i]$，总价值也加$w[i]$，能选的前提是 $j\ge v[i]\&\&k\ge m[i]$。

可得状态转移方程：
$dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k])$
$dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-v[i]][k-m[i]]+w[i])(j\ge v[i]\&\&k\ge m[i])$

初始化

求最大价值，并且总价值也是从0开始加的，直接将所有位置初始化成0即可。

AC代码

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 105;int dp[1010][N][N];
int v[1010], m[1010], w[1010];int main(){int n, m1, m2;cin >> n >> m1 >> m2;for(int i = 1; i <= n; i++){cin >> v[i] >> m[i] >> w[i];}for(int i = 1; i <= n; i++){for(int j = 0; j <= m1; j++){for(int k = 0; k <= m2; k++){dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k]);if(j >= v[i] && k >= m[i]) dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - v[i]][k - m[i]] + w[i]);}}}cout << dp[n][m1][m2] << endl;return 0;
}

混合背包问题

例题

7. 混合背包问题

状态表示

观察上面的几种背包问题可以看出，01背包、完全背包、多重背包其实都是一样的，都是：

$dp[i][j]$表示所有从前$i$个物品中选，所选物品总体积不超过$j$的最大价值。

状态计算

就是将上面三个背包的状态计算结合到一起，先判断一下是什么背包，然后用对应的方程转移即可。

for(遍历所有物品){if(是01背包) 套用01背包代码;else if(是完全背包)套用完全背包代码;else if(是多重背包)套用多重背包代码;
}

初始化

求最大价值，并且总价值也是从0开始加的，直接将所有位置初始化成0即可。

TLE代码

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;int dp[N][N];
int v[N], w[N], s[N];int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> v[i] >> w[i] >> s[i];}for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){if(s[i] == -1 && j >= v[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);else if(s[i] == 0){for(int k = 0; k * v[i] <= j; k++) dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);}else{for(int k = 0; k <= s[i] && k * v[i] <= j; k++) dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);}}}cout << dp[n][m] << endl;return 0;
}

TLE的原因是朴素的分组背包复杂度太高，需要用二进制优化（下文）

背包问题求方案数

对于给定的一个背包容量、物品费用、其他关系等的问题，求装到一定容量的方案总数。

这种问题就是把求最大值换成求和即可。

比如下面这题–01背包求方案数

例题

278. 数字组合

状态表示

和01背包相同，就是将总体积不超过$j$变成了总体积恰好为$j$，把总价值换成了方案数。

• 集合：所有从前$i$个物品中选，所选物品总体积恰好为$j$的方案
• 属性：方案数

$dp[i][j]$表示所有从前$i$个物品中选，所选物品总体积恰好为$j$的方案数。

状态计算

求方案数就是累加，其他和01背包相同。

$dp[i][j]+=dp[i-1][j]$
$dp[i][j]+=dp[i-1][j-v[i]](j\ge v[i])$

初始化

$dp[1][0]$是从$dp[0][0]$转移过来的，$dp[0][0]$是什么都不选，只有这一种方案，方案数为1。

AC代码

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 10005;int dp[105][N];
int v[105];int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> v[i];}dp[0][0] = 1;for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){dp[i][j] += dp[i - 1][j];if(j >= v[i]) dp[i][j] += dp[i - 1][j - v[i]];}}cout << dp[n][m] << endl;return 0;
}

背包问题求具体方案

例题

12. 背包问题求具体方案

分析

一般而言，背包问题是要求一个最优值，如果要求输出这个最优值的方案，可以参照一般动态规划问题输出方案的方法：记录下每个状态的最优值是由状态转移方程的哪一项推出来的，换句话说，记录下它是由哪一个策略推出来的。便可根据这条策略找到上一个状态，从上一个状态接着向前推即可。

int v = V;  // 记录当前的存储空间// 因为最后一件物品存储的是最终状态，所以从最后一件物品进行循环
for (从最后一件循环至第一件) {if (g[i][v]) {选了第 i 项物品;v -= 第 i 项物品的重量;} else {未选第 i 项物品;}
}

而对于求字典序最小的方案，可以从状态转移来分析一下：

对于从$1$到$n$中的每个物品，有三种情况：

• 只能选，则必须选。
• 不能选，则必不选。
• 可选课不选，则必须选。（在前面的物品能选的情况下优先选择前面的物品）

为了满足上面的条件，可以从第$n$个物品遍历到第$1$个物品，每次求出当前背包的最大总价值$dp[1][m]$

然后再从第$1$个物品遍历到第$n$个物品，其中$dp[i][j]$为当前的最优情况，此时若满足：

• $dp[i][j]==dp[i+1][j]$ ，则表示$dp[i][j]$是由$dp[i+1][j]$转移过来的。
• $dp[i][j]==dp[i+1][j-v[i]]+w[i]$，则表示$dp[i][j]$是由$dp[i+1][j-v[i]]$转移过来的。

这时，如果上面两个只满足一个，是“不选”转移过来的就不用管，是“选”转移过来的就输出，并减掉对应的体积即可。如果两个都满足的话，为了保证字典序最小，也要输出并减掉对应的体积。（可选可不选的时候一定选。）

AC代码

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;
int dp[N][N];
int v[N], w[N];int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> v[i] >> w[i];}for(int i = n; i >= 1; i--){for(int j = 0; j <= m; j++){dp[i][j] = dp[i + 1][j];if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i + 1][j - v[i]] + w[i]);}}int j = m;for(int i = 1; i <= n; i++){if(j >= v[i] && dp[i][j] == dp[i + 1][j - v[i]] + w[i]){cout << i << ' ';j -= v[i];}}cout << endl;return 0;
}

背包问题求最优选法方案数

例题

11. 背包问题求方案数

状态表示

和01背包求方案数思路大致相同，但要开两个数组，一个记录最优方案，一个记录方案数。

$dp[i][j]$表示所有从前$i$个物品中选，所选物品总体积恰好为$j$的最大价值。

$cnt[i][j]$表示所有从前$i$个物品中选，所选物品总体积恰好为$j$，并且价值达到$dp[i][j]$的方案数。

状态计算

首先$dp$数组和01背包的更新完全一致，主要来看$cnt$数组是怎么更新的。

这里要注意一个关键点：价值达到$dp[i][j]$的方案数。

那你就要想：它的价值是怎么达到$dp[i][j]$的。

是不是有两种方式，一种是不选（$dp[i-1][j]$），一种是选（$dp[i-1][j-v[i]]+w[i]$），这两个取max，转移来的$dp[i][j]$，那是不是$dp[i][j]$一定等于二者中较大的，并且是由较大的那个分支转移过来的。

$dp[i][j]$由哪个状态转移过来，$cnt[i][j]$就要累加哪个分支。

如果 $dp[i][j]=dp[i-1][j]$ 且 $dp[i][j]\ne dp[i-1][j-v[i]]+w[i]$，说明我们此时不选择把物品放入背包更优，$dp[i][j]$由 $dp[i-1][j]$ 转移过来，$cnt[i][j]+=cnt[i-1][j]$

如果 $dp[i][j]\ne dp[i-1][j]$ 且 $dp[i][j]=dp[i-1][j-v[i]]+w[i]$，说明我们此时选择把物品放入背包更优，$dp[i][j]$由 $dp[i-1][j-v[i]]+w[i]$ 转移过来,$cnt[i][j]+=cnt[i-1][j-v[i]]$

如果 $dp[i][j]=dp[i-1][j]$ 且 $dp[i][j]=dp[i-1][j-v[i]]+w[i]$，说明放入或不放入都能取得最优解， $dp[i][j]$由 $dp[i-1][j]$ 和 $dp[i-1][j-v[i]]+w[i]$ 转移过来, $cnt[i][j]+=cnt[i-1][j]$, $cnt[i][j]+=cnt[i-1][j-v[i]];$

如果理解不了的话，从图论跑最长路、最长路计数的角度想一下：

if(dp[i - 1][j] > dp[i][j]){dp[i][j] = dp[i - 1][j]; // dp[i][j] == dp[i - 1][j]就说明是从dp[i - 1][j]转移过来的cnt[i][j] += cnt[i - 1][j];
}if(dp[i - 1][j - v[i]] + w[i] > dp[i][j]{dp[i][j] = dp[i - 1][j - v[i]] + w[i]; // dp[i][j] == dp[i - 1][j - v[i]] + w[i]就说明是从dp[i - 1][j - v[i]]转移过来的cnt[i][j] += cnt[i - 1][j - v[i]];
}

初始化

$cnt[1][0]$是从$cnt[0][0]$转移过来的，$cnt[0][0]$是什么都不选，只有这一种方案，方案数为1。

需要注意，$dp$数组的初始化和普通的01背包不太一样：普通的01背包的$j$表示总体积不超过$j$，是存在“没装满”的情况的，而当前定义的是总体积恰好等于$j$，一定不存在“没装满”的情况，那怎么从根源上避免这种“没装满”的情况呢？

想一下，所有的那些“没装满”的状态，都是由哪几个“起点”转移过去的，也就是最极限的“没装满”是哪几个状态。

可以看一下下标为0的几个位置，对于所有的$dp[0][j]$，一个物品都没选，还能有总体积？所有的“没装满”的状态都是由这些“起点”转移过去的，所以给这些点都初始化成负无穷，不让他们转移，就从根源上筛掉了所有的“没装满”的状态。

AC代码1

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;
const int mod = 1e9 + 7;int dp[N][N], cnt[N][N];
int v[N], w[N];int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> v[i] >> w[i];}for(int i = 1; i <= m; i++) dp[0][i] = -0x3f3f3f3f;cnt[0][0] = 1;for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){dp[i][j] = max(dp[i][j], dp[i - 1][j]);if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}}for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){if(dp[i][j] == dp[i - 1][j]) cnt[i][j] = (cnt[i][j] + cnt[i - 1][j]) % mod;if(j >= v[i] && dp[i][j] == dp[i - 1][j - v[i]] + w[i]) cnt[i][j] = (cnt[i][j] + cnt[i - 1][j - v[i]]) % mod;}}int res = 0;for(int i = 0; i <= m; i++){if(dp[n][i] == dp[n][m]) res = (res + cnt[n][i]) % mod;}cout << res << endl;return 0;
}

AC代码2

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;
const int mod = 1e9 + 7;int dp[N][N], cnt[N][N];
int v[N], w[N];int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> v[i] >> w[i];}for(int i = 1; i <= m; i++) dp[0][i] = -0x3f3f3f3f;cnt[0][0] = 1;for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){int no = dp[i - 1][j];if(no > dp[i][j]){dp[i][j] = no;cnt[i][j] = cnt[i - 1][j];}else if(dp[i - 1][j] == dp[i][j]){cnt[i][j] += cnt[i - 1][j];}if(j >= v[i]){int yes = dp[i - 1][j - v[i]] + w[i];if(yes > dp[i][j]){dp[i][j] = yes;cnt[i][j] = cnt[i - 1][j - v[i]];}else if(yes == dp[i][j]){cnt[i][j] = (cnt[i][j] + cnt[i - 1][j - v[i]]) % mod;}}}}int res = 0;for(int i = 0; i <= m; i++){if(dp[n][i] == dp[n][m]) res = (res + cnt[n][i]) % mod;}cout << res << endl;return 0;
}

图论写法

像这种$dp$求方案数、求方案的题，都可以可以将其转化为图论中在DAG上的最短路的问题，感兴趣可以自己写一下。

小优化

根据贪心原理，当费用相同时，只需保留价值最高的；当价值一定时，只需保留费用最低的；当有两件物品 $i$,$j$ 且 $i$ 的价值大于 $j$ 的价值并且 $i$ 的费用小于 $j$ 的费用时，只需保留 $i$。

滚动数组优化dp

什么是滚动数组

$dp$的问题最常用的优化之一：滚动数组优化$dp$状态表示，主要用来优化空间。

滚动数组优化了什么

对于有的题，$dp$的状态有很多个，$dp$数组也要开很多维，空间严重超限（比如$dp[1000][1000][1000]$），这个时候，如果状态转移的某一维满足某些条件，就可以用滚动数组将$dp$数组的其中一维优化成$2$（比如$dp[2][1000][1000]$），甚至有的时候还可以直接优化掉一维。

滚动数组优化01背包

下面用01背包问题为例。

01背包的状态转移方程：
$dp[i][j]=max(dp[i][j],dp[i-1][j])$
$dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i])(j\ge v[i])$

可以看到，对于每次状态转移，都是$dp[i-1][...]$向$dp[i][...]$转移，也就是每次转移时，$dp$的第一维用到的空间只有$2$，那可不可以每次让$dp$第一维只开$2$，然后让现在的$i$变成在这两维之间来回滚动呢？

观察一下，对于所有的$i$和$i+1$，是不是只要$i$是奇数，$i+1$就必然是偶数；只要$i$是偶数，$i+1$就必然是奇数；

那在每次表示和转移$dp$数组时都给第一维$\%2$，或者给第一维$\&1$，是不是就实现了在$0$和$1$之间反复滚动？

拿$i\%2$举例子：

• 如果$i$是奇数，$i\%2=1$，$(i-1)\%2=0$，实际上就是$dp[0][...]$向$dp[1][...]$转移，这时$i+1$是偶数，下一次又是$dp[1][...]$向$dp[0][...]$转移，这时的$dp[0][...]$已经是$(i+1)-2$的结果了，覆盖不会影响$i+1$的结果，所以可以这么做。
• 如果$i$是偶数也同理。

就是这样让$dp$数组的某一维在$0$和$1$之间来回滚动，从而优化掉一维空间，这种优化方式就叫滚动数组。

ACcode

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;int dp[2][N];
int v[N], w[N];int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> v[i] >> w[i];}for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){dp[i & 1][j] = dp[i - 1 & 1][j];if(j >= v[i]) dp[i & 1][j] = max(dp[i - 1 & 1][j], dp[i - 1 & 1][j - v[i]] + w[i]);} }cout << dp[n & 1][m] << endl;return 0;
}

滚动数组直接彻底优化掉01背包的一维

观察上面的代码，容易发现：在每个阶段开始时，实际上执行了一次从$dp[i-1][]$到$dp[i][]$的拷贝操作（$dp[i\&1][j]=dp[i-1\&1][j]$），这提示我们可以进一步省略掉$dp$数组的第一维，只用一维数组，即当外层循环到第$i$个物品时，$dp[j]$表示背包中放的物品的总体积不超过$j$的最大价值和。

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;int dp[N];
int v[N], w[N];int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> v[i] >> w[i];}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]);} }cout << dp[m] << endl;return 0;
}

但如果直接优化掉一维的话，遍历体积的一维一定要倒序循环，为什么呢？

每次$dp$更新时，都是由$dp[i-1][]$向$dp[i][]$更新，每一次用到的一定是上一层的数据。
把$dp[i-1][j-v[i]]+w[i]->dp[i][j]$换成一维的话，就是$dp[j-v[i]]+w[i]->dp[j]$，当我们从小到大更新时， 因为$j-v[i]$ 是严格小于$j$ 的，所以我们可以举个例子 $dp[3]=max(dp[3],dp[2]+1)$ 因为我们是从小到大更新的，所以当更新到$dp[3]$的时候，$dp[2]$已经更新过了，已经不是上一层的$dp[2]$。

那这样会产生什么样的效果呢？为什么这样不行呢？想一下，更新$dp$数组，一定是先遍历$i$、后遍历$j$，每次遍历$j$的时候实际上$i$是确定的，也就是同一个物品。如果$dp[j-v[i]]$在前面已经被更新过了，也就是说前面的转移过程是$dp[j-v[i]-v[i]]+w[i]->dp[j-v[i]]$，如果后面再拿$dp[j-v[i]]$去更新$dp[j]$，也就是$dp[j-v[i]]+w[i]->dp[j]$，那最后的效果就是$dp[j-2\ast v[i]]+2\ast w[i]$，那是不是意味着在当前$dp[j]$这个状态，第$i$个物品被选了两次？如果在后面再更新，还会被选更多次，这就和01背包一件物品只能选一次冲突了。

倒序遍历体积就避免了上面的问题。

滚动数组优化完全背包

弄懂滚动数组优化01背包为什么要倒序遍历体积后，在刚才的过程中想一想，如果正序遍历，就会出现一个物品可以选多次的情况，那一个物品选多次，不就是完全背包吗？所以在01背包滚动数组优化成一维的基础上，正序遍历体积，就变成了滚动数组优化完全背包，比如上面的完全背包问题，下面就是它的AC代码。

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;int dp[N];
int v[N], w[N];int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> 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]);} }cout << dp[m] << endl;return 0;
}

二进制优化多重背包

例题

多重背包问题 II

分析

优化的本质就是：用二进制的思想将每个物品可以选的次数$s$拆分。

首先，将多重背包转化成最朴素的01背包：也就是每种物品有$s$个，将每一个都看成是01背包中的1个物品，每个物品都只有选$0$个和选$1$个这两种选法。

但这样来选，复杂度太高了，可不可以将某些物品放在一堆呢？

比如第$i$件物品有$s$件：

首先，朴素的多重背包问题，是不是要从$1$~$s$遍历一遍？

那如果能将这$s$个物品分成几堆，通过选这几堆其中的几堆物品，他们的和能凑出来从$1$~$s$的所有情况，是不是就可以通过遍历这几堆来替代这层枚举了?

进而想到，任何一个数都有它的二进制表示，任何一个数都可以表示成若干二的整数次幂的和。

举个例子：对于$s=1023$:

用$2^0$可以凑出来$0$~$1$的每个数。
用$2^0$和$2^1$可以凑出来$0$~$3$的每个数。
用$2^0$和$2^1$和$2^2$可以凑出来$0$~$7$的每个数。
…
所以用 $2^0$ ~ $2^9$一定可以凑出从$0$~$1023$的每个数。

那如果$s$不是2的整数次幂减一怎么办呢？这个时候只需要在后面再补一个$s-（前面几项2^k的和）$就可以了。

比如对于$s=10$
用$2^0$可以凑出来$0$~$1$的每个数。
用$2^0$和$2^1$可以凑出来$0$~$3$的每个数。
用$2^0$和$2^1$和$2^2$可以凑出来$0$~$7$的每个数。
用$2^0$和$2^1$和$2^2$和$3$可以凑出来从$0$~$10$的每个数。

那这样分堆有什么用呢？

仔细想想，从$1$~$s$之间的每一个数都能用上面这几个堆的数凑出来，是不是每种凑法就相当于是这个数的一个二进制表示（除了多最后一个数的时候）？

而一个数的二进制表示只有0和1，那是不是问题可以转化为01背包？

事实上，最后多出来那个非$2^k$的数在凑数的时候也只能选0或1次。

那为什么不直接把它也用一个$>s$的$2^k$的数来表示呢？

还是上面的例子：
对于$s=10$
用$2^0$可以凑出来$0$~$1$的每个数。
用$2^0$和$2^1$可以凑出来$0$~$3$的每个数。
用$2^0$和$2^1$和$2^2$可以凑出来$0$~$7$的每个数。
用$2^0$和$2^1$和$2^2$和$3$可以凑出来从$0$~$10$的每个数。
用$2^0$和$2^1$和$2^2$和$2^3$可以凑出来从$0$~$15$的每个数。

如果最后组数放$2^3$个而不是$3$个，就会凑出来选$11$~$15$次的情况，而实际上是不能选这么多次的，因此这样凑是错的。

把对于每组物品能选$1$~$s$次，转化成每堆物品只能选$0$或$1$次，01背包的每种选法恰好等同于分组背包的每种选法，内层循环时间复杂度由$O(s)$降到了$O(logs)$。

AC代码

#include <iostream>
#include <vector>
#define endl '\n'
const int N = 10010, M = 2010;
using namespace std;int dp[M];int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n, m;cin >> n >> m;vector<int> v, w;for(int i = 0; i < n; i++){int a, b, s;cin >> a >> b >> s;int t = 1;while(t <= s){v.push_back(a * t);w.push_back(b * t);s -= t;t *= 2;}        if(s){v.push_back(a * s);w.push_back(b * s);}}n = v.size();for(int i = 0; i < n; i++){for(int j = m; j >= v[i]; j--){dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}cout << dp[m] << endl;return 0;
}

为什么这样拆分是对的？

如果直接遍历转化为01背包问题，是每次都拿一个来问，取了好还是不取好，假如10个取7个最优，那么在实际的遍历过程中在第7个以后经过状态转移方程其实已经是选择“不取”好了。

现在，用二进制思想将其分堆，分成$k+1$个分别有$2^k$个的堆，然后拿这一堆一堆去问，我是取了好呢，还是不取好呢，经过dp选择之后，结果和拿一个一个来问的结果是完全一样的，因为dp选择的是最优结果，而任意一个实数都可以用二进制来表示，如果最终选出来10个取7个是最优的，在分堆的选择过程中分成了$2^0=1,2^1=2,2^2=4,2^3=8$这四堆，然后去问四次，也就是拿去走dp状态转移方程，走的结果是第一堆1个，取了比不取好，第二堆2个，取了比不取好，第三堆四个，取了比不取好，第四堆8个，取了还不如不取，最后依旧是取了$1+2+4=7$个。

为什么是这样呢？因为dp本身就是用来比较哪个更优的，在状态转移的过程中自然会完成上述询问得出相应结果，这也就是说，无论最终取几个是最优解，用二进制取出来的结果和一次一次问是完全一样的。

二进制分堆能不重不漏的表示到所有情况，一个一个遍历也能遍历到所有情况，而dp每一步的状态转移都取的是当前的最优解，两者都做到了不重不漏，逐渐递推到全局，也一定是全局的最优解。

一篇写的很好的文章

背包问题九讲 - 崔添翼