Knapsack Problem Note
Posted on 2020-04-13 Edited on 2020-04-16
做一个背包问题的合集
方便之后抄板子/不是
01背包问题
有一个固定体积的背包，并有n个可以选择的物品，每个物品只有一个，每个物品有一定的价值和体积。求在背包总体积下能容纳的物品的最大价值。
时间复杂度：O(nm)
空间复杂度：O(m)
//从大到小枚举体积
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, f[N];
int main()
{
cin >> n >> m;
for (int i = 0; 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];
}完全背包问题
有一个固定体积的背包，并有n个可以选择的物品，每个物品的数量有无限个，每个物品有一定的体积和价值。求在背包总体积下能容纳的物品最大值。
时间复杂度：O(nm)
空间复杂度：O(m)
//从小到大枚举体积
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, f[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++)
{
int v, w;
cin >> v >> w;
for (int j = v; j <= m; j ++)
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m];
}多重背包问题
有一个固定体积的背包，并有n个可以选择的物品，每个物品的数量有s个，每个物品有一定的体积和价值。求在背包总体积下能容纳的物品最大值。
朴素版的多重背包问题
时间复杂度：O(nms)
空间复杂度：O(m)
//三重循环，分别枚举物品，体积和数量
#include <iostream>
using namespace std;
const int N = 110;
int n, m, f[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++)
{
int v, w, s;
cin >> v >> w >> s;
for (int j = m; j >= 0; j --)
for (int k = 0; k <= s && v * k <= j; k ++)
f[j] = max(f[j], f[j - v * k] + w * k);
}
cout << f[m];
}二进制优化版的多重背包问题
时间复杂度：O(nmlogs)
空间复杂度：O(m)
//将物品以二进制拆开 转化为01背包问题
#include <vector>
#include <iostream>
using namespace std;
const int N = 2010;
int n, m, f[N];
int main()
{
cin >> n >> m;
vector<pair<int, int>> g;
for (int i = 0; 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 ++)
for (int j = m; j >= g[i].first; j --)
f[j] = max(f[j], f[j - g[i].first] + g[i].second);
cout << f[m];
}单调队列优化版的多重背包问题
时间复杂度：O(nm)
空间复杂度：O(m)
//单调队列优化
#include <cstring>
#include <iostream>
using namespace std;
const int N = 20010;
int n, m, f[N], g[N], q[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++)
{
int v, w, s;
cin >> v >> w >> s;
memcpy(g, f, sizeof f);
for (int r = 0; r < v; r ++)
{
int hh = 0, tt = -1;
for (int k = r; k <= m; k += v)
{
if (hh <= tt && q[hh] < k - s * v) hh ++;
if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
while (hh <= tt && g[q[tt]] - (q[tt] - r) / v * w <= g[k] - (k - r) / v * w) tt --;
q[++ tt] = k;
}
}
}
cout << f[m];
}分组背包问题
有一个固定体积的背包，并有n组可以选择的物品，每组物品有若干个，每一组内的物品最多只能选一个。求在背包总体积下能容纳的物品最大值。
时间复杂度：O(nms)
空间复杂度：O(m)
//依次枚举物品，体积和决策
#include <iostream>
using namespace std;
const int N = 110;
int n, m, f[N], v[N], w[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++)
{
int s;
cin >> s;
for (int j = 0; j < s; j ++) cin >> v[j] >> w[j];
for (int j = m; j >= 0; j --)
for (int k = 0; k < s; k ++)
if (j >= v[k])
f[j] = max(f[j], f[j - v[k]] + w[k]);
}
cout << f[m];
}混合背包问题
把01背包，完全背包和多重背包混在一起。每个单独处理即可。
#include <vector>
#include <iostream>
using namespace std;
const int N = 1010;
int f[N], n, m;
struct T
{
int k, v, w;
};
vector<T> t;
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++)
{
int v, w, s;
cin >> v >> w >> s;
if (s <= 0) t.push_back({s, v, w});
else
{
for (int k = 1; k <= s; k *= 2)
{
s -= k;
t.push_back({-1, k * v, k * w});
}
if (s) t.push_back({-1, s * v, s * w});
}
}
for (auto i : t)
{
if (i.k == -1)
for (int j = m; j >= i.v; j --) f[j] = max(f[j], f[j - i.v] + i.w);
else
for (int j = i.v; j <= m; j ++) f[j] = max(f[j], f[j - i.v] + i.w);
}
cout << f[m];
}二维费用的背包问题
有一个固定体积和质量限制的背包，并有n个可以选择的物品，每个物品只有一个，每个物品有一定的价值，体积和质量。求在背包总体积和质量限制下能容纳的物品的最大价值。
时间复杂度：O(nvm)
空间复杂度：O(vm)
#include <iostream>
using namespace std;
const int S = 1010;
int N, V, M, f[S][S];
int main()
{
cin >> N >> V >> M;
for (int i = 0; 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];
}背包问题求方案数
求最优选法的方案数。
时间复杂度：O(nm)
空间复杂度：O(m)
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N], g[N], n, m;
int main()
{
cin >> n >> m;
for (int i = 0; i <= m; i ++) g[i] = 1;
for (int i = 0; i < n; i ++)
{
int v, w;
cin >> v >> w;
for (int j = m; j >= v; j --)
{
int t = max(f[j], f[j - v] + w);
int s = 0;
if (t == f[j]) s += g[j];
if (t == f[j - v] + w) s += g[j - v];
if (s >= mod) s -= mod;
g[j] = s, f[j] = t;
}
}
cout << g[m];
}背包问题求具体方案
输出背包问题的具体方案。
时间复杂度：O(nm)
空间复杂度：O(m2)
//不能优化空间，正常求解，之后从后向前反推
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, v[N], w[N], f[N][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])
cout << i << " ", j -= v[i];
}题单
01背包
1. 采药
裸题。
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, f[N];
int main()
{
cin >> m >> n;
for (int i = 0; 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];
}2. 打怪
循环中加一个判断。
#include <iostream>
using namespace std;
const int N = 5010;
int f[N], n, w, A, B;
int main()
{
cin >> n >> w >> A >> B;
for (int i = 0; i < n; i ++)
{
int x, y;
cin >> x >> y;
if (A + B < x) continue;
for (int j = w; j >= y; j --)
f[j] = max(f[j], f[j - y] + 1);
}
cout << f[w];
}3. 装箱问题
将物品的体积作为价值。
#include <iostream>
using namespace std;
const int N = 20010;
int n, m, f[N];
int main()
{
cin >> m >> n;
for (int i = 0; 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];
}4. 开心的金明
#include <iostream>
using namespace std;
const int N = 30010;
int n, m, f[N];
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++)
{
int v, w;
cin >> v >> w;
w *= v;
for (int j = m; j >= v; j --)
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m];
}完全背包问题
1. 货币系统
挖掘性质
- a1,a2,a3,…一定可以被表示出来。
- b1,b2,b3,…一定不可以被其他bi表示出来。
- 在最优解中b1,b2,…一定是从a1,a2,…中选择的。
若ai可以被表示，则必不选，否则必选。
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 25010;
int T, n, res;
int a[N], f[M];
int main()
{
cin >> T;
while (T --)
{
cin >> n;
for (int i = 0; i < n; i ++) cin >> a[i];
sort(a, a + n);
memset(f, 0, sizeof f);
f[0] = 1, res = 0;
for (int i = 0; i < n; i ++)
{
if (f[a[i]] == 0) res ++;
for (int j = a[i]; j <= a[n - 1]; j ++)
f[j] += f[j - a[i]];
}
cout << res << endl;
}
}多重背包问题
1. 庆功会
朴素版的多重背包问题复杂度为O(nms)，在这里3×107足够，所以直接上最暴力的板子就完事了。
#include <iostream>
using namespace std;
const int N = 6010;
int n, m, f[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++)
{
int v, w, s;
cin >> v >> w >> s;
for (int j = m; j >= 0; j --)
for (int k = 0; k <= s && v * k <= j; k ++)
f[j] = max(f[j], f[j - v * k] + w * k);
}
cout << f[m];
}分组背包问题
1. 机器分配
#include <iostream>
using namespace std;
const int N = 20;
int n, m, f[N][N], w[N][N];
int res[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 <= j; k ++)
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 >= 0; i --)
for (int k = 0; k <= j; k ++)
if (f[i][j] == f[i - 1][j - k] + w[i][k])
{
res[i] = k, j -= k;
break;
}
for (int i = 1; i <= n; i ++) cout << i << " " << res[i] << endl;
}二维费用的背包问题
1. 宠物小精灵之收服
#include <iostream>
using namespace std;
int V1, V2, K, f[1010][510];
int main()
{
cin >> V1 >> V2 >> K;
for (int i = 0; i < K; i ++)
{
int v1, v2;
cin >> v1 >> v2;
for (int j = V1; j >= v1; j --)
for (int k = V2 - 1; k >= v2; k --)
f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
}
cout << f[V1][V2 - 1] << " ";
int v2 = V2 - 1;
while (v2 > 0 && f[V1][V2 - 1] == f[V1][v2 - 1]) v2 --;
cout << V2 - v2;
}2. 潜水员
状态表示：所有从前i个物品中选，且氧气含量至少是j，氮气含量至少是k的所有选法中的最小值。
状态转移：
- 不包含物品
i的选法：f[i - 1][j][k] - 包含物品
i的选法：f[i - 1][max(0, j - v1)][max(0, k - v2)] + w
#include <cstring>
#include <iostream>
using namespace std;
int V1, V2, K, f[22][80];
int main()
{
cin >> V1 >> V2 >> K;
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
for (int i = 0; i < K; i ++)
{
int v1, v2, w;
cin >> v1 >> v2 >> w;
for (int j = V1; j >= 0; j --)
for (int k = V2; k >= 0; k --)
f[j][k] = min(f[j][k], f[max(0, j - v1)][max(0, k - v2)] + w);
}
cout << f[V1][V2];
}背包问题求方案数
1. 数字组合
本题的数据范围较大，需要使用__int128_t或者高精度来编写，但AcWing上的数据集较弱，请读者自行用以下这组数据测试。
输入样例
100 10000
200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200输出样例
100891344545564193334812497256#include <iostream>
using namespace std;
const __int128_t N = 10010;
__int128_t n, m, f[N], g[N];
template <typename T>
inline T read()
{
T sum = 0, fl = 1;
int ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-')
fl = -1;
for (; isdigit(ch); ch = getchar())
sum = sum * 10 + ch - '0';
return sum * fl;
}
template <typename T>
inline void write(T x)
{
if (x < 0) x = -x, putchar('-');
static T sta[35];
T top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) putchar(sta[--top] + '0');
}
int main()
{
n = read<__int128_t>(), m = read<__int128_t>();
for (int i = 0; i < m; i ++) g[i] = 1;
for (int i = 0; i < n; i ++)
{
__int128_t v;
v = read<__int128_t>();
for (int j = m; j >= v; j --)
{
__int128_t s = 0, t = max(f[j], f[j - v] + v);
if (t == f[j]) s += g[j];
if (t == f[j - v] + v) s += g[j - v];
g[j] = s, f[j] = t;
}
}
write<__int128_t>(g[m]);
}2. 买书
方案数+完全背包问题 一 模 一 样。
#include <iostream>
using namespace std;
const int N = 1010;
int f[N], g[N], n, m;
int p[4] = {10, 20, 50, 100};
int main()
{
cin >> m; n = 4;
g[0] = 1;
for (int i = 0; i < n; i ++)
{
int v = p[i], w = p[i];
for (int j = v; j <= m; j ++)
{
int t = max(f[j], f[j - v] + w);
int s = 0;
if (t == f[j]) s += g[j];
if (t == f[j - v] + w) s += g[j - v];
g[j] = s;
f[j] = t;
}
}
cout << g[m];
}3. 货币系统
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 3010;
ll n, m, f[N], g[N];
int main()
{
cin >> n >> m;
g[0] = 1;
for (int i = 0; i < n; i ++)
{
ll v;
cin >> v;
for (int j = v; j <= m; j ++)
{
ll t = max(f[j], f[j - v] + v);
ll s = 0;
if (t == f[j]) s += g[j];
if (t == f[j - v] + v) s += g[j - v];
g[j] = s, f[j] = t;
}
}
cout << g[m];
}Related Posts