01 背包
AcWing 423. 采药
代价： 采药时间 T
价值： w
0 - 1背包问题
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int f[N];
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i ++ ) {
int v, w;
cin >> v >> w;
for (int j = m; j >= v; j -- ) {
f[j] = max(f[j], f[j - v] + w);
}
}
cout << f[m];
return 0;
}
AcWing 1024. 装箱问题
总代价： 箱子容量 V
代价： 小物品体积
价值： 小物品体积
0-1背包问题
#include <bits/stdc++.h>
using namespace std;
const int N = 20010;
int n, m;
int f[N];
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i ++ ) {
int v;
cin >> v;
for (int j = m; j >= v; j -- ) {
f[j] = max(f[j], f[j - v] + v);
}
}
cout << m - f[m];
return 0;
}
AcWing 1022. 宠物小精灵之收服
代价： v1 精灵球数量， v2 皮卡丘体力值
价值： 收服小精灵的数量
双重代价的 0-1 背包问题
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N][N];
int V1, V2, w;
int n, m;
int main() {
cin >> V1 >> V2 >> w;
for (int i = 1; i <= w; i ++ ) {
int v1, v2;
cin >> v1 >> v2;
for (int j = V1; j >= v1; j -- ) {
for (int k = V2; k >= v2; k -- ) {
f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
}
}
}
// 得皮卡丘体力小于等于0的野生小精灵不会被小智收服。
cout << f[V1][V2 - 1] << " ";
int j = V2 - 1;
while (j > 0 && f[V1][j - 1] == f[V1][V2 - 1]) j -- ;
cout << V2 - j;
return 0;
}
AcWing 278. 数字组合
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int f[N];
int n, m;
int main() {
cin >> n >> m;
f[0] = 1;
for (int i = 1; i <= n; i ++ ) {
int v;
cin >> v;
for (int j = m; j >= v; j -- ) {
f[j] += f[j - v];
}
}
cout << f[m];
return 0;
}
AcWing 426. 开心的金明
#include <bits/stdc++.h>
using namespace std;
const int N = 30010;
int n, m;
int f[N];
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i ++ ) {
int v, w;
cin >> v >> w;
w = v * w;
for (int j = m; j >= v; j -- ) {
f[j] = max(f[j], f[j - v] + w);
}
}
cout << f[m];
return 0;
}
AcWing 734. 能量石
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, m, T;
int f[N];
struct Stone{
int s, e, l;
bool operator < (const Stone &t) const {
return s * t.l < l * t.s;
}
}stone[N];
int main() {
cin >> T;
int cnt = T;
while (T -- ) {
cin >> n;
m = 0;
for (int i = 1; i <= n; i ++ ) {
int s, e, l;
cin >> s >> e >> l;
stone[i] = {s, e, l};
m += s;
}
sort(stone + 1, stone + n + 1);
memset (f, -0x3f, sizeof f);
f[0] = 0;
for (int i = 1; i <= n; i ++ ) {
int s = stone[i].s, e = stone[i].e, l = stone[i].l;
for (int j = m; j >= s; j -- ) {
f[j] = max(f[j], f[j - s] + e - (j - s) * l);
}
}
int res = 0;
for (int i = 1; i <= m; i ++ ) res = max(res, f[i]);
printf("Case #%d: %d\n", cnt - T, res);
}
return 0;
}
完全背包问题
AcWing 1023. 买书
方案数转移：设定 f[0] = 1, 当满足条件 - v 时，变可得到 0， 实现方案数量的累加
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int m;
int v[5] = {0, 10, 20, 50, 100};
int f[N];
int main() {
cin >> m;
f[0] = 1;
for (int i = 1; i <= 4; i ++ ) {
for (int j = v[i]; j <= m; j ++ ) {
f[j] += f[j - v[i]];
}
}
cout << f[m];
return 0;
}
AcWing 1021. 货币系统
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
typedef long long LL;
int n, m;
LL f[N];
int main() {
cin >> n >> m;
f[0] = 1;
for (int i = 1; i <= n; i ++ ) {
int v;
cin >> v;
for (int j = v; j <= m; j ++ ) {
f[j] += f[j - v];
}
}
cout << f[m];
return 0;
}
AcWing 532. 货币系统
- 利用完全背包求每个数的方案数后，如果等于 1 ，说明只能被自己所表示，则一定要选出来，组成最小的系统。
#include <bits/stdc++.h>
using namespace std;
const int N = 25010;
int f[N], v[N];
int n, T, m;
int main() {
cin >> T;
while (T -- ) {
cin >> n;
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ ) cin >> v[i], m = max(v[i], m);
f[0] = 1;
for (int i = 1; i <= n; i ++ ) {
for (int j = v[i]; j <= m; j ++ ) {
f[j] += f[j - v[i]];
}
}
int ans = 0;
for (int i = 1; i <= n; i ++ ) {
if (f[v[i]] == 1) ans ++;
}
cout << ans << endl;
}
return 0;
}
多重背包问题
AcWing 6. 多重背包问题 III
- 将多重背包利用二进制优化为 01 背包问题
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
typedef pair<int, int> PII;
int n, m;
int f[N];
vector<PII> G;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) {
int v, w, s;
cin >> v >> w >> s;
for (int k = 1; k <= s; k *= 2) {
s -= k;
G.push_back({v*k, w*k});
}
if (s > 0) G.push_back({v*s, w*s});
}
for (int i = 0; i <= G.size(); i ++ ) {
int v = G[i].first, w = G[i].second;
for (int j = m; j >= v; j -- ) {
f[j] = max(f[j], f[j - v] + w);
}
}
cout << f[m];
return 0;
}
AcWing 1019. 庆功会
#include <bits/stdc++.h>
using namespace std;
const int N = 6010;
typedef pair<int, int> PII;
int n, m;
int f[N];
vector<PII> G;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) {
int v, w, s;
cin >> v >> w >> s;
for (int k = 1; k < s; k *= 2) {
s -= k;
G.push_back({k * v, k * w});
}
if (s) G.push_back({s * v, s * w});
}
for (int i = 0; i < G.size(); i ++ ) {
int v = G[i].first, w = G[i].second;
for (int j = m; j >= v; j -- ) {
f[j] = max(f[j], f[j - v] + w);
}
}
cout << f[m];
return 0;
}
混合背包问题
AcWing 7. 混合背包问题
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int f[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) {
int v, w, s;
cin >> v >> w >> s;
if (s == -1) {
for (int j = m; j >= v; j -- ) {
f[j] = max(f[j], f[j - v] + w);
}
} else if (s == 0) {
for (int j = v; j <= m; j ++ ) {
f[j] = max(f[j], f[j - v] + w);
}
} else {
for (int k = 1; k <= s; k *= 2) {
for (int j = m; j >= k * v; j -- ) {
f[j] = max(f[j], f[j - k * v] + k * w);
}
s -= k;
}
if (s) {
for (int j = m; j >= s * v; j -- ) {
f[j] = max(f[j], f[j - s * v] + s * w);
}
}
}
}
cout << f[m];
return 0;
}
二维费用的背包问题
AcWing 8. 二维费用的背包问题
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N];
int V, M, n;
int main() {
cin >> n >> V >> M;
for (int i = 1; i <= n; i ++ ) {
int v, m, w;
cin >> v >> m >> w;
for (int j = V; j >= v; j -- ) {
for (int k = M; k >= m; k -- ) {
f[j][k] = max(f[j][k], f[j - v][k - m] + w);
}
}
}
cout << f[V][M];
return 0;
}
AcWing 1020. 潜水员
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int f[N][N];
int V, M, n;
int main() {
cin >> V >> M >> n;
memset (f, 0x3f, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= n; i ++ ) {
int v, m, w;
cin >> v >> m >> w;
for (int j = V; j >= 0; j -- ) {
for (int k = M; k >= 0; k -- ) {
// 如果超过容量的就用 f[0][0] 这个状态来取，此时一定不会比最小值小
f[j][k] = min(f[j][k], f[max(0, j - v)][max(0, k - m)] + w);
}
}
}
cout << f[V][M];
return 0;
}
分组背包问题
AcWing 1013. 机器分配
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int n, m;
int f[N][N], w[N][N];
int way[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
cin >> w[i][j];
}
}
for (int i = 1; i <= n; i ++ ) {
for (int j = 0; j <= m; j ++ ) {
for (int k = 0; k <= m; k ++ ) {
if (k <= j) f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
}
}
}
cout << f[n][m] << endl;
int j = m;
for (int i = n; i >= 1; i -- ) {
for (int k = 0; k <= j; k ++ ) {
if (f[i][j] == f[i - 1][j - k] + w[i][k]) {
way[i] = k;
j -= k;
break;
}
}
}
for (int i = 1; i <= n; i ++ ) cout << i << " " << way[i] << endl;
return 0;
}
背包求方案数
AcWing 11. 背包问题求方案数
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, m;
int f[N], cnt[N];
int main() {
cin >> n >> m;
for (int i = 0; i <= m; i ++ ) {
cnt[i] = 1;
}
for (int i = 1; i <= n; i ++ ) {
int v, w;
cin >> v >> w;
for (int j = m; j >= v; j -- ) {
int value = f[j - v] + w;
if (f[j] < f[j - v] + w) {
f[j] = f[j - v] + w;
cnt[j] = cnt[j - v];
} else if (f[j] == f[j - v] + w) {
cnt[j] += cnt[j - v];
}
cnt [j] %= mod;
}
}
cout << cnt[m];
return 0;
}
AcWing 12. 背包问题求具体方案
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int f[N][N], v[N], w[N];
int main() {
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 ++ ) {
f[i][j] = f[i + 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
}
}
int j = m;
for (int i = 1; i <= n; i ++ ) {
if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
j -= v[i];
cout << i << " ";
}
}
return 0;
}