1. IT分享知识网首页
  2. 未分类

背包九讲（超详细 ：算法分析 + 问题分析 + 代码分析）

老牧童 • • 未分类

背包九讲（超详细 ：算法分析 + 问题分析 + 代码分析）背包问题 1 01 背包问题 2 完全背包问题 3 多重背包问题 4 混合背包问题 5 二维费用的背包问题 6 分组背包问题 7 背包问题求方案数 8 求背包问题的方案 9 有依赖的背包问题 1 01 背包问题特点

大家好，欢迎来到IT知识分享网。

背包问题

1. 01背包问题

特点：每个物品只能用一次，只能是选择或者不选择

第 i 件物品的体积是 vi，价值是 wi。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围

输入样例：

4 5 1 2 2 4 3 4 4 5

输出样例：

8

f [ i ][ j ] 表示只看前 i 个物品，总体积是 j 的情况下，总价值最大是多少

result = max { f [ n ][ 0 ~ v ] }

f [ 0 ][ 0 ] = 0;

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<stack> #include<queue> #include<sstream> using namespace std; typedef long long ll; const int N=1010; int f[N][N]; int v[N], w[N]; int n, m; int main() { 
    cin >> n >> m; for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; f[0][0] = 0; for(int i = 1; i <= n; 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 ans = 0; for(int i = 0; i <= m; i ++ ) ans = max(ans, f[n][i]); cout << ans << endl; return 0; }

result = max { f[ 0 ~ v ] }; => result = f [ m ]

for(int i = 1; i <= n; i ++ ) for(int j = m; j >= v[i]; j -- ) f[j] = max(f[j], f[j - v[i]] + w[i]);

f [ j ] = max {1, 2};

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<stack> #include<queue> #include<sstream> using namespace std; typedef long long ll; const int N=1010; int f[N]; int v[N], w[N]; int n, m; 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 = m; j >= v[i]; j -- ) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m]; return 0; }

2. 完全背包问题

特点：每种物品有无限个，可以选择 0~n 个

题目链接

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围

输入样例：

4 5 1 2 2 4 3 4 4 5

输出样例：

10

f [ i ] 表示总体积是 i 的情况下，最大价值是多少

result = max { f [ 0 ~ m ] };

f [ i ] :

 for(int i = 1; i <= n; i ++ ) for(int j = v[i]; j <= m; j ++ ) f[j] = max([j], [j - v[i]] + w[i]); 
#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<stack> #include<queue> #include<sstream> using namespace std; typedef long long ll; const int N=1010; int f[N]; int v[N], w[N]; int n, m; 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 = v[i]; j <= m; j ++ ) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m]; return 0; }

3. 多重背包问题

特点：每件物品有 s 件，对于每件物品可以选择 0 ~ s 件

题目链接

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围

输入样例：

4 5 1 2 3 2 4 1 3 4 3 4 5 2

输出样例：

10

f [ i ] 表示总体积是 i 的情况下，最大值是多少

f [ i ] :

for(int i = 1; i <= n; i ++ ) for(int j = m; j >= v[i]; j -- ) f[j] = max(f[j], f[j - 1 * v[i]] + 1 * w[i], f[j - 2 * v[i]] + 2 * w[i] ... ) 
#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<stack> #include<queue> #include<sstream> using namespace std; typedef long long ll; const int N=1010; int f[N]; int v[N], w[N], s[N]; int n, m; 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 = m; j >= v[i]; j -- ) for(int k = 0; k <= s[i] && k * v[i] <= j; k ++ ) f[j] = max(f[j], f[j - k * v[i]] + k * w[i]); cout << f[m]; return 0; }

题目链接

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围

提示：

本题考查多重背包的二进制优化方法。

输入样例

4 5 1 2 3 2 4 1 3 4 3 4 5 2

输出样例：

10

二进制优化

利用这个方法，我们就可以把数据范围为 2000 的数量变成了 log22000 ≈ 11 ，这样我们在继续实现多重背包就可以了

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<stack> #include<queue> #include<sstream> using namespace std; typedef long long ll; const int N=1010; int f[N]; int v[N], w[N], s[N]; int n, m; struct Good{ 
    int v, w; }; int main() { 
    vector<Good> good; cin >> n >> m; for(int i = 0; i < n; i ++ ) cin >> v[i] >> w[i] >> s[i]; for(int i = 0; i < n; i ++ ) { 
    // 二进制处理  for(int j = 1; j <= s[i]; j *= 2 ) { 
    s[i] -= j; good.push_back({ 
   v[i] * j, w[i] * j}); } if(s[i] >= 0) good.push_back({ 
   v[i] * s[i], w[i] * s[i]}); } // 多重背包 for(auto goods : good) for(int j = m; j >= goods.v; j -- ) f[j] = max(f[j], f[j - goods.v] + goods.w); cout << f[m] << endl; return 0; }

题目链接

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围

提示：

本题考查多重背包的单调队列优化方法。

输入样例

4 5 1 2 3 2 4 1 3 4 3 4 5 2

输出样例：

10 
#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<stack> #include<queue> #include<sstream> using namespace std; typedef long long ll; const int N=20010; int n, m; int v[N], w[N], s[N]; int f[N], g[N], q[N]; int main() { 
    cin >> n >> m; for(int i = 0; i < n; i ++ ) cin >> v[i] >> w[i] >> s[i]; for(int i = 0; i < n; i ++ ) { 
    // 滚动数组  memcpy(g, f, sizeof f); for(int j = 0; j < v[i]; j ++ ) { 
    int hh = 0, tt = -1; for(int k = j; k<= m; k += v[i]) { 
    if(hh <= tt && q[hh] < k - s[i] * v[i]) hh ++ ; while(hh <= tt && g[q[tt]] - (q[tt] - j) / v[i] * w[i] <= g[k] - (k - j) / v[i] * w[i]) tt -- ; q[ ++ tt] = k; f[k] = g[q[hh]] + (k - q[hh]) / v[i] * w[i]; } } } cout << f[m] << endl; return 0; }

4. 混合背包问题

特点：包含01背包、完全背包、多重背包三种背包问题

题目链接

有 N 种物品和一个容量是 V 的背包。

物品一共有三类：

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

si=−1 表示第 i 种物品只能用1次；
si=0 表示第 i 种物品可以用无限次；
si>0 表示第 i 种物品可以使用 si 次；
输出格式
输出一个整数，表示最大价值。



数据范围

输入样例

4 5 1 2 -1 2 4 1 3 4 0 4 5 2

输出样例：

8

对于多重背包，我们利用二进制优化后，也就是二进制分组后，对于每一组都相当于01背包，所以在标记背包种类的时候，要标记成01背包

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<stack> #include<queue> #include<sstream> using namespace std; typedef long long ll; const int N=1010; int n, m; int v[N], w[N], s[N]; int f[N]; struct Good{ 
    int kind; int v, w; }; vector<Good> good; int main() { 
    cin >> n >> m; for(int i = 0; i < n; i ++ ) cin >> v[i] >> w[i] >> s[i]; for(int i = 0; i < n; i ++ ) { 
    if(s[i] == -1) good.push_back({ 
   -1, v[i], w[i]}); else if(s[i] == 0) good.push_back({ 
   0, v[i], w[i]}); // 多重背包二进制优化（分组）之后，对于每一组都相当于是01背包  else { 
    for(int k = 1; k <= s[i]; k *= 2) { 
    s[i] -= k; good.push_back({ 
   -1, v[i] * k, w[i] * k}); } if(s[i] > 0) good.push_back({ 
   -1, v[i] * s[i], w[i] * s[i]}); } } // 对于01背包和完全背包分两种情况状态转移即可  for(auto goods : good) { 
    // 01背包  if(goods.kind == -1) { 
    for(int j = m; j >= goods.v; j -- ) f[j] = max(f[j], f[j - goods.v] + goods.w); } else { 
    for(int j = goods.v; j <= m; j ++ ) f[j] = max(f[j], f[j - goods.v] + goods.w); } } cout << f[m] << endl; return 0; }

5. 二维费用的背包问题

特点：一般的背包问题，只有一个容量的限制，对于二维背包问题，除了容量的限制还有另一个限制，

题目链接

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

输入格式
第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。

输出格式
输出一个整数，表示最大价值。

数据范围

输入样例

4 5 6 1 2 3 2 4 4 3 4 5 4 5 6

输出样例：

8

f [ i ][ j ] 表示总体积是 i ，总重量是 j 的情况下，最大价值是多少

同时对于状态转移的时候，两层 for 循环，一层是体积限制，一层是重量限制

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<stack> #include<queue> #include<sstream> using namespace std; typedef long long ll; const int N=1010; int a, b, c; int v[N], t[N], w[N]; int f[N][N]; int main() { 
    cin >> a >> b >> c; for(int i = 0; i < a; i ++ ) cin >> v[i] >> t[i] >> w[i]; for(int i = 0; i < a; i ++ ) for(int j = b; j >= v[i]; j -- ) for(int k = c; k >= t[i]; k -- ) f[j][k] = max(f[j][k], f[j - v[i]][k - t[i]] + w[i]); cout << f[b][c] << endl; return 0; }

6. 分组背包问题

特点：每一组中有多个物品，但是同组内的物品最多只能选择一个

题目链接

有 N 组物品和一个容量是 V 的背包。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

接下来有 N 组数据：

每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。


数据范围

输入样例

3 5 2 1 2 2 4 1 3 4 1 4 5

输出样例：

8 
#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<stack> #include<queue> #include<sstream> using namespace std; typedef long long ll; const int N=1010; int n, m, s; 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; }

7. 背包问题求方案数

特点：在背包问题下，求出最优选法的方案数

题目链接

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7 的结果。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示 方案数 模 109+7 的结果。

数据范围

输入样例

4 5 1 2 2 4 3 4 4 6

输出样例：

2

f [ j ] 表示体积恰好是 j 的情况下，最大价值是多少
g [ j ] 表示体积恰好是 j 的情况下，方案数是多少

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<stack> #include<queue> #include<sstream> using namespace std; typedef long long ll; const int N=1010; const int mod = 1e9 + 7; const int INF = 0x3f3f3f3f; int n, m; int v[N], w[N]; int f[N], g[N]; int main() { 
    cin >> n >> m; g[0] = 1; for(int i = 1; i <= m; i ++ ) f[i] = -INF; for(int i = 0; i < n; i ++ ) cin >> v[i] >> w[i]; for(int i = 0; i < n; i ++ ) for(int j = m; j >= v[i]; j -- ) { 
    int t = max(f[j], f[j - v[i]] + w[i]); int s = 0; if(t == f[j]) s += g[j]; if(t == f[j - v[i]] + w[i]) s += g[j - v[i]]; if(s >= mod) s -= mod; f[j] = t; g[j] = s; } int maxx = 0; for(int i = 0; i <= m; i ++ ) maxx = max(maxx, f[i]); int ans = 0; for(int i = 0; i <= m; i ++ ) if(maxx == f[i]) { 
    ans += g[i]; if(ans >= mod) ans -= mod; } cout << ans << endl; return 0; }

8. 求背包问题的方案

特点：在普通背包的基础下，输出选择方案，比如选择物品1 、 3 、 4是最优解，那么就输出 1 、 3 、 4

题目链接

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 1…N。

数据范围

输入样例

4 5 1 2 2 4 3 4 4 6

输出样例：

1 4 
#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<stack> #include<queue> #include<sstream> using namespace std; typedef long long ll; const int N=1010; const int mod = 1e9 + 7; const int INF = 0x3f3f3f3f; 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 vol = m; for(int i = 1; i <= n; i ++ ) if(vol - v[i] >= 0 && f[i][vol] == f[i + 1][vol - v[i]] + w[i]) { 
    cout << i << ' '; vol -= v[i]; } return 0; }

9. 有依赖的背包问题

特点：N个物品，V容量的背包，物品之间有依赖关系，且依赖关系可以构成一棵树，如果选择某一个物品那么就必须先选择这个物品的父亲物品

题目链接

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。

输出格式
输出一个整数，表示最大价值。

数据范围

父节点编号范围：

  • 内部结点：1≤pi≤N;
  • 根节点 pi=−1;

输入样例

5 7 2 3 -1 2 2 1 3 5 1 4 7 2 3 6 2

输出样例：

11

f [ i ][ j ] 表示选择结点 i （在这里也就是根节点），总体积是 j 时，最大价值是多少

当我们选择根节点后，对于根节点的每一棵子树，都相当于对根节点做分组背包了，每一个根节点相当于一个组，对于组中的节点分为选择或者不能选择

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<stack> #include<queue> #include<sstream> using namespace std; typedef long long ll; const int N=1010; int n, m; int v[N], w[N]; int f[N][N]; int h[N], e[N], ne[N], idx; 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 != -1; i = ne[i]) { 
    int son = e[i]; dfs(son); 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]; // 如果选择了子节点后，还没有选择到最后的 root ，那么就不能选择当前结点及其根节点了  for(int i = 0; i < v[u]; i ++ ) f[u][i] = 0; } int main() { 
    cin >> n >> m; memset(h, -1, sizeof h); int root; 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; }

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/110233.html

赞 (0)
老牧童老牧童
0
上一篇 2026-02-01 22:10
下一篇 2026-02-01 22:20

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信