• 欢迎光临~

# [算法模板随笔] 背包Part 1 01背包

01背包大概就是这样一个问题:

f[i][j] = max{f[i - 1][j], f[i - 1][j - v[i]] + w[i]}

``````/*
Author: SJ

general
1.shuzu buyao kai xiaole
2.0 1 zhe liangge tepan
3.dfs jide biaoji qidian
4.changdaima jide fenbu tiaoshi
5.yao xihuanshang heihezi

str
1.yongle s.substr(), jide kanyixiashibushikeyi yigeyige shuchu

THINK TWICE, CODE ONCE.
Duo xiang ti, Shao jiao lv.
*/
#include<bits/stdc++.h>
const int N = 1e3 + 10;
using ll = long long;

int n, m, v[N], w[N], f[N][N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

std::cin >> n >> m;
for (int i = 1; i <= n; i++) std::cin >> v[i] >> w[i];

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = std::max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
std::cout << f[n][m];
return 0;
}
``````

``````/*
Author: SJ

general
1.shuzu buyao kai xiaole
2.0 1 zhe liangge tepan
3.dfs jide biaoji qidian
4.changdaima jide fenbu tiaoshi
5.yao xihuanshang heihezi

str
1.yongle s.substr(), jide kanyixiashibushikeyi yigeyige shuchu

THINK TWICE, CODE ONCE.
Duo xiang ti, Shao jiao lv.
*/
#include<bits/stdc++.h>
const int N = 1e3 + 10;
using ll = long long;

int n, m, v[N], w[N], f[N][N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

std::cin >> n >> m;
for (int i = 1; i <= n; i++) std::cin >> v[i] >> w[i];

for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= m; j++) {
if (j >= v[i]) f[i][j] = std::max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
}
std::cout << f[n][m];
return 0;
}
``````

``````/*
Author: SJ

general
1.shuzu buyao kai xiaole
2.0 1 zhe liangge tepan
3.dfs jide biaoji qidian
4.changdaima jide fenbu tiaoshi
5.yao xihuanshang heihezi

str
1.yongle s.substr(), jide kanyixiashibushikeyi yigeyige shuchu

THINK TWICE, CODE ONCE.
Duo xiang ti, Shao jiao lv.
*/
#include<bits/stdc++.h>
const int N = 1e3 + 10;
using ll = long long;

int n, m, v[N], w[N], f[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

std::cin >> n >> m;
for (int i = 1; i <= n; i++) std::cin >> v[i] >> w[i];

for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
f[j] = std::max(f[j], f[j - v[i]] + w[i]);
}
}
std::cout << f[m];
return 0;
}
``````

1. 为什么第二层循环一定要逆序呢, 实际上啊, 循环开始时, 这个一维数组, 存储的就是原来二维数组f[i - 1]维的所有状态, 假如从大到小循环的话, f[j - v[i]]就会在f[j]前面被更新到, 也就是f[j - v[i]]此时是f[i][j - v[i]]了, 但是我们要的是f[i - 1][j - v[i]], 所以就不对了, 那我们让它逆序循环就好了.
2. 为什么之前我们说过直接优化第二维不太可行, 但是这里又貌似可以了呢. 这是因为之前用二维数组存储状态时, 直接优化第二维会让有些时候第i维需要的i - 1维的状态为0. 但是在这里就不存在这种问题了, 第i - 1维没更新过的状态自然也就等于第i - 2维的状态, 刚好是符合条件的.