背包九讲
- 背包问题
- 完全背包问题
- 多重背包问题 I
- 多重背包问题 II
- 多重背包问题 III
- 混合背包问题
- 二维费用的背包问题
- 分组背包问题
- 有依赖的背包问题
- 背包问题求方案数
- 背包问题求具体方案
背包问题
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
0 < N,V ≤ 1000
0 < vi,wi ≤ 1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
8
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int f[N][N];
int v[N], w[N];
int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) 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] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);}cout << f[n][m] << endl;return 0;
}
完全背包问题
有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。
第 i 种物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
0 < N,V ≤ 1000
0 < vi,wi ≤ 1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
10
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) 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] = max(f[i][j], f[i][j - v[i]] + w[i]);}cout << f[n][m] << endl;return 0;
}
多重背包问题 I
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
0 < N,V ≤ 100
0 < vi,wi,si ≤ 100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];
int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ ) for (int k = 0; k <= s[i] && k * v[i] <= j; k ++ )f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);cout << f[n][m] << endl;return 0;
}
#include <iostream>
using namespace std;
const int N = 10010;
int n, m, cnt = 1;
int v[N], w[N];
int f[N];
int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) {int a, b, c;cin >> a >> b >> c;for (int j = 1; j <= c; j ++ ){v[cnt] = a;w[cnt] = b;cnt ++ ;}}for (int i = 1; i <= cnt; i ++ )for (int j = m; j >= v[i]; j -- ){f[j] = max(f[j], f[j - v[i]] + w[i]);}cout << f[m] << endl;return 0;
}
多重背包问题 II
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
0 < N ≤ 1000
0 < V ≤ 2000
0 < vi,wi,si ≤ 2000
提示:
本题考查多重背包的二进制优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10
#include <iostream>
#include <vector>
using namespace std;
const int N = 2010;
int n, m;
int f[N];
struct Good
{int v, w;
};
vector<Good> goods;
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;goods.push_back({v * k, w * k});}if (s > 0) goods.push_back({s * v, s * w});}for (auto good : goods)for (int j = m; j >= good.v; j -- )f[j] = max(f[j], f[j - good.v] + good.w);cout << f[m] << endl;return 0;
}
多重背包问题 III
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,V (0 < N ≤ 1000, 0 < V ≤ 20000),用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
0 < N ≤ 1000
0 < V ≤ 20000
0 < vi,wi,si ≤ 20000
提示
本题考查多重背包的单调队列优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10
男人八题
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20010;
int n, m;
int 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 j = 0; j < v; j ++ ){int hh = 0, tt = -1;for (int k = j; k <= m; k += v){if (hh <= tt && q[hh] < k - s * v) hh ++ ;while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v* w) tt -- ;q[ ++ tt] = k;f[k] = g[q[hh]] + (k - q[hh]) / v * w;}}}cout << f[m] << endl;return 0;
}
混合背包问题
有 N 种物品和一个容量是 V 的背包。
物品一共有三类:
- 第一类物品只能用1次(01背包);
- 第二类物品可以用无限次(完全背包);
- 第三类物品最多只能用 si 次(多重背包);
每种体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
- si=−1 表示第 i 种物品只能用1次;
- si=0 表示第 i 种物品可以用无限次;
- si>0 表示第 i 种物品可以使用 si 次;
输出格式
输出一个整数,表示最大价值。
数据范围
0 < N,V ≤ 1000
0 < vi,wi ≤ 1000
−1 ≤ si ≤ 1000
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例:
8
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N], s[N];
int f[N];
int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];for (int i = 1; i <= n; i ++ ){if (s[i] == 0) for (int j = v[i]; j <= m; j ++ )f[j] = max(f[j], f[j - v[i]] + w[i]);else {if (s[i] == -1) s[i] = 1;for (int k = 1; k <= s[i]; k *= 2){for (int j = m; j >= k * v[i]; j -- )f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);s[i] -= k;}if (s[i])for (int j = m; j >= s[i] * v[i]; j -- )f[j] = max(f[j], f[j - s[i] * v[i]] + s[i] * w[i]);}}cout << f[m] << endl;return 0;
}
二维费用的背包问题
有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且价值总和最大。
输出最大价值。
输入格式
第一行三个整数,N,V,M,用空格隔开,分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N 行,每行三个整数 vi,mi,wi,用空格隔开,分别表示第 i 件物品的体积、重量和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
0 < N ≤ 1000
0 < V,M ≤ 100
0 < vi,mi ≤ 100
0 < wi ≤ 1000
输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
输出样例:
8
#include <iostream>
using namespace std;
const int NU = 1010;
int N, V, M;
int v[NU], m[NU], w[NU];
int f[NU][NU];
int main()
{cin >> N >> V >> M;for (int i = 1; i <= N; i ++ ) cin >> v[i] >> m[i] >> w[i];for (int i = 1; i <= N; i ++ )for (int j = V; j >= v[i]; j -- )for (int k = M; k >= m[i]; k -- )f[j][k] = max(f[j][k], f[j - v[i]][k - m[i]] + w[i]);cout << f[V][M] << endl;return 0;
}
分组背包问题
三重循环
- 物品种类
- 枚举背包体积
- 枚举决策:当前种类物品的数量
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N,V,用空格隔开,分别表示物品组数和背包容量。
接下来有 N 组数据:
- 每组数据第一行有一个整数 Si,表示第 i 个物品组的物品数量;
- 每组数据接下来有 Si 行,每行有两个整数 vij,wij,用空格隔开,分别表示第 i 个物品组的第 j 个物品的体积和价值;
输出格式
输出一个整数,表示最大价值。
数据范围
0 < N,V ≤ 100
0 < Si ≤ 100
0 < vij,wij ≤ 100
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例:
8
没完全搞懂
分组背包问题,先枚举物品组,然后枚举体积,内部枚举决策
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N];
int f[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] << endl;return 0;
}
有依赖的背包问题
有 N 个物品和一个容量是 V 的背包。
物品之间具有依赖关系,且依赖关系组成一棵树的形状。如果选择一个物品,则必须选择它的父节点。
如下图所示:
如果选择物品5,则必须选择物品1和2。这是因为2是5的父节点,1是2的父节点。
每件物品的编号是 i,体积是 vi,价值是 wi,依赖的父节点编号是 pi。物品的下标范围是 1…N。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N,V,用空格隔开,分别表示物品个数和背包容量。
接下来有 N 行数据,每行数据表示一个物品。
第 i 行有三个整数 vi,wi,pi,用空格隔开,分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1,表示根节点。 数据保证所有物品构成一棵树。
输出格式
输出一个整数,表示最大价值。
数据范围
1 ≤ N,V ≤ 100
1 ≤ vi,wi ≤ 100
父节点编号范围:
- 内部结点:1 ≤ pi ≤ N;
- 根节点 pi=−1;
输入样例
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2
输出样例:
11
每个节点求一个分组背包
没完全懂
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N];
int h[N], e[N], ne[N], idx;
int f[N][N];
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u)
{for (int i = h[u]; ~ i; i = ne[i]) // 物品组 {int son = e[i];dfs(e[i]);// 分组背包 for (int j = m - v[u]; j >= 0; j -- ) // 体积for (int k = 0; k <= j; k ++ ) // 决策f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]); }// 加入u for (int i = m; i >= v[u]; i -- ) f[u][i] = f[u][i - v[u]] + w[u];for (int i = 0; i < v[u]; i ++ ) f[u][i] = 0;
}
int main()
{int root;cin >> n >> m;memset(h, -1, sizeof h);for (int i = 1; i <= n; i ++ ){int p;cin >> v[i] >> w[i] >> p;if (p == -1) root = i;else add(p, i);}dfs(root);cout << f[root][m] << endl;return 0;
}
背包问题求方案数
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出 最优选法的方案数。注意答案可能很大,请输出答案模 109+7 的结果。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数,表示 方案数 模 109+7 的结果。
数据范围
0 < N,V ≤ 1000
0 < vi,wi ≤ 1000
输入样例
4 5
1 2
2 4
3 4
4 6
输出样例:
2
没完全掌握
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, m;
int v[N], w[N];
int f[N], g[N];
int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];memset(f, -0x3f, sizeof f);f[0] = 0;g[0] = 1;for (int i = 1; i <= n; i ++ )for (int j = m; j >= v[i]; j -- ){int maxv = max(f[j], f[j - v[i]] + w[i]);int s = 0;if (f[j] == maxv) s = g[j];if (f[j - v[i]] + w[i] == maxv) s = (s + g[j - v[i]]) % mod;f[j] = maxv;g[j] = s;} int res = 0;for (int i = 1; i <= m; i ++ )if (f[i] > f[res])res = i;int sum = 0; for (int i = 0; i <= m; i ++ )if (f[i] == f[res])sum = (sum + g[i]) % mod;cout << sum << endl;return 0;
}
背包问题求具体方案
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出 字典序最小的方案。这里的字典序是指:所选物品的编号所构成的序列。物品的编号范围是 1…N。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式
输出一行,包含若干个用空格隔开的整数,表示最优解中所选物品的编号序列,且该编号序列的字典序最小。
物品编号范围是 1…N。
数据范围
0 < N,V ≤ 1000
0 < vi,wi ≤ 1000
输入样例
4 5
1 2
2 4
3 4
4 6
输出样例:
1 4
没完全掌握
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int 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];}return 0;
}