背包
01背包
#include <iostream>
using namespace std;
const int MAXN = 1005;
int n, V;
int v[MAXN], p[MAXN], f[MAXN];
int Max (int x, int y) {return x > y ? x : y;}
int main () {
cin >> n >> V;
for (int i = 1; i <= n; i++) cin >> v[i] >> p[i];
for (int i = 1; i <= n; i++)
for (int j = V; j >= v[i]; j--)
f[j] = Max (f[j], f[j - v[i]] + p[i]);
cout << f[V];
return 0;
}
完全背包
#include <iostream>
using namespace std;
const int MAXN = 1005;
int n, m;
int f[MAXN];
int v[MAXN], p[MAXN];
int Max (int x, int y) {return x > y ? x : y;}
int main () {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> p[i];
}
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= m; j++) {
f[j] = Max (f[j], f[j - v[i]] + p[i]);
}
}
cout << f[m];
return 0;
}
多重背包
1.朴素
#include <iostream>
using namespace std;
const int MAXN = 105;
int n, m;
int f[MAXN];
int v[MAXN], p[MAXN], num[MAXN];
int Max (int x, int y) {return x > y ? x : y;}
int Min (int x, int y) {return x < y ? x : y;}
int main () {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> p[i] >> num[i];
}
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
for (int k = 1; k <= Min (num[i], j / v[i]); k++) {
f[j] = Max (f[j], f[j - k * v[i]] + k * p[i]);
}
}
}
cout << f[m];
return 0;
}
2.二进制优化
#include <iostream>
using namespace std;
const int MAXN = 100005;
int n, m, len;
int f[MAXN];
int v[MAXN], p[MAXN];
int Max (int x, int y) {return x > y ? x : y;}
int Min (int x, int y) {return x < y ? x : y;}
int main () {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int _v, _p, _num;
cin >> _v >> _p >> _num;
for (int j = 1; j <= _num; j <<= 1) {
_num -= j;
len++, v[len] = _v * j, p[len] = _p * j;
}
if (_num != 0) {
len++, v[len] = _v * _num, p[len] = _p * _num;
}
}
for (int i = 1; i <= len; i++) {
for (int j = m; j >= v[i]; j--) {
f[j] = Max (f[j], f[j - v[i]] + p[i]);
}
}
cout << f[m];
return 0;
}
3.单调队列优化
混合背包问题
#include <iostream>
using namespace std;
const int MAXN = 10005;
int n, m, len;
int f[MAXN];
int v[MAXN], p[MAXN];
bool flag[MAXN];
int Max (int x, int y) {return x > y ? x : y;}
int main () {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int _v, _p, _num;
cin >> _v >> _p >> _num;
if (_num > 0) {
for (int j = 1; j <= _num; j <<= 1) {
_num -= j;
len++, v[len] = _v * j, p[len] = _p * j;
}
if (_num != 0) len++, v[len] = _v * _num, p[len] = _p * _num;
}
else {
len++, v[len] = _v, p[len] = _p;
if (_num == 0) flag[len] = 1;
}
}
for (int i = 1; i <= len; i++) {
if (flag[i] == 1) {
for (int j = v[i]; j <= m; j++) {
f[j] = Max (f[j], f[j - v[i]] + p[i]);
}
}
else {
for (int j = m; j >= v[i]; j--) {
f[j] = Max (f[j], f[j - v[i]] + p[i]);
}
}
}
cout << f[m];
return 0;
}
Processed:
0.032, SQL:
8
