目录
牛客DP41 【模板】01背包
问题一解析
问题二解析
解析代码
滚动数组优化代码
牛客DP41 【模板】01背包
【模板】01背包_牛客题霸_牛客网
#include <iostream>
using namespace std;
int main() {
int a, b;
while (cin >> a >> b) { // 注意 while 处理多个 case
cout << a + b << endl;
}
}
// 64 位输出请用 printf("%lld")问题一解析
背包问题的状态表示非常经典，如果不知道怎么来的，可以先把它当成一个模板。
以某个位置为结尾，结合题目要求，定义一个状态表示：
dp[i][j] 表示：从前 i 个物品中挑选，总体积不超过 j ，所有的选法中，能挑选出来的最大价值。
状态转移方程：
线性 dp 状态转移方程分析方式，一般都是根据最后一步的状况，来分情况讨论：
- 不选第 i 个物品：相当于就是去前 i - 1 个物品中挑选，并且总体积不超过 j 。此时 dp[i][j] = dp[i - 1][j] ;。
- 选择第 i 个物品：那么就只能去前 i - 1 个物品中，挑选总体积不超过 j - v[i] 的物品。此时 dp[i][j] = dp[i - 1][j - v[i]] + w[i] ; 。但是这种状态不一定存在，要判断 j >= v[i]。
综上，状态转移方程为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) ;
初始化、填表顺序、返回值：
多加一行，方便初始化，此时仅需将第一行初始化为 0 即可。因为什么也不选，也能满足体积不小于 j 的情况，此时的价值为 0 。填表顺序从左往右，最后返回dp[n][V] ;
问题二解析
第二问仅需微调一下 dp 过程的五步即可。 因为有可能凑不齐 j 体积的物品，因此把不合法的状态设置为 -1 。
以某个位置为结尾，结合题目要求，定义一个状态表示：
dp[i][j] 表示：从前 i 个物品中挑选，总体积正好等于 j ，所有的选法中，能挑选出来的最大价值。
状态转移方程：
线性 dp 状态转移方程分析方式，一般都是根据最后一步的状况，来分情况讨论：
- 不选第 i 个物品：相当于就是去前 i - 1 个物品中挑选，并且总体积不超过 j 。此时 dp[i][j] = dp[i - 1][j] ;。
- 选择第 i 个物品：那么就只能去前 i - 1 个物品中，挑选总体积不超过 j - v[i] 的物品。此时 dp[i][j] = dp[i - 1][j - v[i]] + w[i] ; 。但是这种状态不一定存在，不仅要判断 j >= v[i] ，还要判断 dp[i - 1][j - v[i]] 表示的情况是否存在，也就是 dp[i - 1][j - v[i]] != -1 。
综上，状态转移方程为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) ;
初始化、填表顺序、返回值：
多加一行，方便初始化，第一行第一个格子为 0 ，因为正好能凑齐体积为 0 的背包，但是第一行第一个格子后面都是 -1 ，因为没有物品，无法满足体积大于 0 的情况。第一列全为0。
填表顺序从左往右，最后返回dp[n][V] ;
解析代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010; // OJ定义成全局方便，且空间不会轻易溢出
int n, V, v[N], w[N];
int dp[N][N];
int main()
{
cin >> n >> V;
for (int i = 1; i <= n; ++i) // 从1开始读数据
{
cin >> v[i] >> w[i];
}
for(int i = 1; i <= n; ++i)
{
for(int j = 0; j <= V; ++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][V] << endl;
memset(dp, 0, sizeof(dp));
for(int j = 1; j <= V; ++j)
{
dp[0][j] = -1;
}
for(int i = 1; i <= n; ++i)
{
for(int j = 0; j <= V; ++j)
{
dp[i][j] = dp[i - 1][j];
if(j >= v[i] && dp[i - 1][j - v[i]] != -1)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
}
}
cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
return 0;
}
滚动数组优化代码
背包问题基本上都是利用滚动数组来做空间上的优化：（时间也有常数的优化）
- 利用滚动数组优化。
- 直接在原始代码上修改。
第i行元素只依赖于第i-1行元素。理论上，只需要保持两行元素，所以只需两个数组交替滚动，就能完成dp数组的填充。因此空间复杂度从O（N^2） 变为O（N）。
这里还可以直接用一个数组来进行优化：从前往后去更新数组，dp[j - v[ i ]]肯定不比dp[ j ]的值大，而改了前面，后面的更新就会用到前面更新的数据，而本来应该使用原二维数组 i - 1行的数据，也就是更新数据之前的，因此可以巧妙地从后往前遍历，这样就可以避免用到更新后的数据。
在01背包问题中，优化的结果为：
- 删掉所有的横坐标。
- 修改一下 j 的遍历顺序。
（滚动数组优化代码只需能在原代码上修改就行，不用考虑什么状态表示）
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010; // OJ定义成全局方便，且空间不会轻易溢出
int n, V, v[N], w[N];
// int dp[N][N];
int dp[N]; // 滚动数组优化，把所有dp表左边一维坐标删掉，修改遍历顺序
int main()
{
cin >> n >> V;
for (int i = 1; i <= n; ++i) // 从1开始读数据
{
cin >> v[i] >> w[i];
}
for(int i = 1; i <= n; ++i)
{
for(int j = V; j >= v[i]; --j) // 滚动数组优化
{
dp[j] = dp[j];
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[V] << endl;
memset(dp, 0, sizeof(dp));
for(int j = 1; j <= V; ++j)
{
dp[j] = -1;
}
for(int i = 1; i <= n; ++i)
{
for(int j = V; j >= v[i]; --j) // 滚动数组优化
{
if(dp[j - v[i]] != -1)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
return 0;
}
