1. 首页首页
  2. 编程基础编程基础

背包问题至多，至少，恰好问题的研究

编程基础 • • 阅读 12

背包问题至多，至少，恰好问题的研究背包问题初始化 至多 至少 恰好问题 c 恰好装满背包

写在开头：
本文参考：https://www.acwing.com/blog/content/458/
仅作为笔记使用

目录

Ⅰ. 结论

一. 求方案数初始化总结

1. 二维情况

  1. 体积至多是j，f[0][i]=1,0<=i<=m，其余是0
  2. 体积恰好是j，f[0][0]=1，其余是0
  3. 体积至少j，f[0][0]=1,其余是0

2. 一维情况

  1. 体积至多j，f[i]=1，0<=i<=m
  2. 体积恰好j,f[0]=1，其余是0
  3. 体积至少j，f[0]=1,其余是0

求最大值和最小值初始化总结

1. 二维情况

  1. 体积至多是j，f[i,k]=0,0<=i<=m,0<=k<=m
  2. 体积恰好是j，
    当前价值的最小值：f[0][0]=0，其余是INF
    当求价值的最大值:f[0][0]=0，其余是-INF
  3. 体积至少j,f[0][0]=0，其余是INF （只会求价值最小值）

2. 一维情况

  1. 体积至多j，f[i]=0，0<=i<=m（只会求价值的最大值）
  2. 体积恰好j
    当求价值的最小值：f[0]=0，其余是INF
    当求价值的最大值:f[0]=0，其余是-INF
  3. 体积至少j，f[0]=0，其余是INF（只 会求价值最小值）

Ⅱ . 具体问题

一. 求方案数问题

  1. 从前i个物品中选，总体积不超过j的总方案数,初始化f[0][i]=1，0<=i<=m其余是0
    01背包
    每个物品有一定的体积，只能选一次，求总体积不超过m的方案数
    二维code
#include <bits/stdc++.h> using namespace std; const int N = 110; int f[N][N]; int n, m; int main() { 
    cin >> n >> m; for (int i = 0; i <= m; i++)f[0][i] = 1; for (int i = 1; i <= n; i++) { 
    int v; cin >> v; for (int j = 0; j <= m; j++) { 
    f[i][j] = f[i - 1][j]; if (j >= v)f[i][j] += f[i - 1][j - v]; } } cout << f[n][m] << endl; return 0; }

一维code

#include <bits/stdc++.h> using namespace std; const int N = 110; int f[N]; int n, m; int main() { 
    cin >> n >> m; for (int i = 0; i <= m; i++)f[i] = 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] << endl; return 0; }

完全背包
给你一堆物品，每个物品有一定的体积，每个物品可以选无数多个，总体积不超过m的方案数
二维code

#include <bits/stdc++.h> using namespace std; const int N = 110; int n, m; int f[N][N]; int main() { 
    cin >> n >> m; for (int i = 0; i <= m; i++) f[0][i] = 1; for (int i = 1; i <= n; i++) { 
    int v; cin >> v; for (int j = 0; j <= m; j++) { 
    f[i][j] = f[i - 1][j]; if (j >= v) f[i][j] += f[i][j - v]; } } cout << f[n][m] << endl; return 0; }

一维code

#include <bits/stdc++.h> using namespace std; const int N = 110; int n, m; int f[N]; int main() { 
    cin >> n >> m; for (int i = 0; i <= m; i++) f[i] = 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] << endl; return 0; }
  1. 从前 i 个物品中选，且总体积恰好是j的方案数,初始化为f[0][0]=1其余是0

01背包
给你一堆物品，每个物品有一定的体积，每个物品只能选一个，求总体积恰好是m的方案数
二维code

#include <bits/stdc++.h> using namespace std; const int N = 110; int n, m; int f[N][N]; int main() { 
    cin >> n >> m; f[0][0] = 1; for (int i = 1; i <= n; i++) { 
    int v; cin >> v; for (int j = 0; j <= m; j++) { 
    f[i][j] = f[i - 1][j]; if (j >= v)f[i][j] += f[i - 1][j - v]; } } cout << f[n][m] << endl; return 0; }

一维code

#include <bits/stdc++.h> using namespace std; const int N = 110; int n, m; int f[N]; 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] << endl; return 0; }

完全背包
给你一堆物品，每个物品有一定的体积，每个物品可以选无数多个，求总体积恰好是m的方案数
二维code

#include <bits/stdc++.h> using namespace std; const int N = 110; int n, m; int f[N][N]; int main() { 
    cin >> n >> m; f[0][0] = 1; for (int i = 1; i <= n; i++) { 
    int v; cin >> v; for (int j = 0; j <= m; j++) { 
    f[i][j] = f[i - 1][j]; if(j>=v)f[i][j] += f[i][j - v]; } } cout << f[n][m] << endl; return 0; }

一维code

#include <bits/stdc++.h> using namespace std; const int N = 110; int n, m; int 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] << endl; return 0; }
  1. 从前i个物品中选，总体积至少是j的总方案数，初始化f[0][0]=1,其余至少是0,至少的情况，j需要从0枚举到m，或者从m枚举到0）
    01背包
    给你一堆物品，每个物品有一定的体积，每个物品只能选一个，求总体积至少是m的方案数
#include <iostream> using namespace std; const int N = 110; int n, m; int f[N][N]; int main() { 
    cin >> n >> m; f[0][0] = 1; for (int i = 1; i <= n; i++) { 
    int v; cin >> v; for (int j = 0; j <= m; j++)//即使物品体积比j大，j - v < 0，也能选，等价于f[i - 1][0] { 
    f[i][j] = f[i - 1][j] + f[i - 1][max(0, j - v)]; } } cout << f[n][m] << endl; return 0; }

一维code

#include <iostream> using namespace std; const int N = 110; int n, m; int f[N]; int main() { 
    cin >> n >> m; f[0] = 1; for (int i = 1; i <= n; i++) { 
    int v; cin >> v; for (int j = m; j >= 0; j--)//即使物品体积比j大，j - v < 0，也能选，等价于f[i - 1][0] { 
    f[j] += f[max(0, j - v)]; } } cout << f[m] << endl; return 0; }

二. 求最大值最小值问题

  1. 从前i个物品中选，且总体积不超过j的最大价值，初始化是f[i,k] = 0，0 <= i <= n, 0 <= k <= m（只会求价值的最大值）

01背包问题
给你一堆物品，每个物品有一定的体积和对应的价值，每个物品只能选一个，求总体积不超过m的最大价值
二维code

#include <bits/stdc++.h> using namespace std; const int N = 110; int f[N][N]; int n, m; int main() { 
    cin >> n >> m; for (int i = 1; i <= n; i++) { 
    int w, v; cin >> v >> w; for (int j = 0; j <= m; j++) { 
    f[i][j] = f[i - 1][j]; if (j >= v)f[i][j] = max(f[i][j], f[i - 1][j - v] + w); } } cout << f[n][m] << endl; return 0; }

一维code

#include <bits/stdc++.h> using namespace std; const int N = 110; int f[N]; int n, m; int main() { 
    cin >> n >> m; for (int i = 1; i <= n; i++) { 
    int w, v; cin >> v >> w; for (int j = m; j >= v; j--) { 
    f[j] = max(f[j], f[j - v] + w); } } cout << f[m] << endl; return 0; }
  1. 从前i个物品中选，且总体积恰好是j
    求价值最小值：初始化f[0][0] = 0, 其余是INF
    01背包
    给你一堆物品，每个物品有一定的体积和对应的价值，每个物品只能选一个，求总体积恰好是j的最小价值
    二维code
#include <bits/stdc++.h> using namespace std; const int N = 110; int f[N][N]; int n, m; int main() { 
    cin >> n >> m; memset(f, 0x3f, sizeof f); f[0][0] = 0; for (int i = 1; i <= n; i++) { 
    int v, w; cin >> v >> w; for (int j = 0; j <= m; j++) { 
    f[i][j] = f[i - 1][j]; if (j >= v)f[i][j] = min(f[i][j], f[i - 1][j - v] + w); } } cout << f[n][m] << endl; return 0; }

一维code

#include <bits/stdc++.h> using namespace std; const int N = 110, INF = 0x3f3f3f3f; int n, m; int f[N]; int main() { 
    cin >> n >> m; memset(f, INF, sizeof f); f[0] = 0; for(int i = 1;i <= n;i ++) { 
    int v, w; cin >> v >> w; for(int j = m;j >= v;j --) { 
    f[j] = min(f[j], f[j - v] + w); } } cout << f[m] << endl; return 0; }
  1. 求价值最大值：初始化f[0][0] = 0, 其余是-INF
    给你一堆物品，每个物品有一定的体积和对应的价值，每个物品只能选一个，求总体积恰好是j的最大价值
    二维code
#include <bits/stdc++.h> using namespace std; const int N = 110, INF = 0x3f3f3f3f; int n, m; int f[N][N]; int main() { 
    cin >> n >> m; memset(f, -INF, sizeof f); f[0][0] = 0; for(int i = 1;i <= n;i ++) { 
    int v, w; cin >> v >> w; for(int j = 0;j <= m;j ++) { 
    f[i][j] = f[i - 1][j]; if(j >= v) f[i][j] = max(f[i][j], f[i - 1][j - v] + w); } } cout << f[n][m] << endl; return 0; }

一维code

#include <iostream> #include <cstring> using namespace std; const int N = 110, INF = 0x3f3f3f3f; int n, m; int f[N]; int main() { 
    cin >> n >> m; memset(f, -INF, sizeof f); f[0] = 0; 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] << endl; return 0; }

完全背包

  1. 求价值最小值：初始化f[0][0] = 0, 其余是INF
    给你一堆物品，每个物品有一定的体积和对应的价值，每个物品可以选无数多个，求总体积恰好是j的最小价值
#include <bits/stdc++.h> using namespace std; const int N = 110, INF = 0x3f3f3f3f; int n, m; int f[N][N]; int main() { 
    cin >> n >> m; memset(f, INF, sizeof f); f[0][0] = 0; for (int i = 1; i <= n; i++) { 
    int v, w; cin >> v >> w; for (int j = 0; j <= m; j++) { 
    f[i][j] = f[i - 1][j]; if (j >= v) f[i][j] = min(f[i][j], f[i][j - v] + w); } } cout << f[n][m] << endl; return 0; }

一维code

#include <bits/stdc++.h> using namespace std; const int N = 110, INF = 0x3f3f3f3f; int n, m; int f[N]; int main() { 
    cin >> n >> m; memset(f, INF, sizeof f); f[0] = 0; for (int i = 1; i <= n; i++) { 
    int v, w; cin >> v >> w; for (int j = v; j <= m; j++) { 
    f[j] = min(f[j], f[j - v] + w); } } cout << f[m] << endl; return 0; }
  1. 求价值最大值：初始化f[0][0] = 0, 其余是-INF
    给你一堆物品，每个物品有一定的体积和对应的价值，每个物品可以选无数多个，求总体积恰好是j的最大价值
    二维code
#include <iostream> #include <cstring> using namespace std; const int N = 110, INF = 0x3f3f3f3f; int n, m; int f[N][N]; int main() { 
    cin >> n >> m; memset(f, -INF, sizeof f); f[0][0] = 0; for (int i = 1; i <= n; i++) { 
    int v, w; cin >> v >> w; for (int j = 0; j <= m; j++) { 
    f[i][j] = f[i - 1][j]; if (j >= v) f[i][j] = max(f[i][j], f[i][j - v] + w); } } cout << f[n][m] << endl; return 0; }

一维code

#include <iostream> #include <cstring> using namespace std; const int N = 110, INF = 0x3f3f3f3f; int n, m; int f[N]; int main() { 
    cin >> n >> m; memset(f, -INF, sizeof f); f[0] = 0; for(int i = 1;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] << endl; return 0; }

3、从前i个物品中选，且总体积至少是j，初始化是f[0][0] = 0, 其余是INF（只会求价值的最小值）

例子：给你一堆物品，每个物品有一定的体积和对应的价值，每个物品可以选无数多个，求总体积至少是j的最小价值
二维code

#include <iostream> #include <cstring> using namespace std; const int N = 110, INF = 0x3f3f3f3f; int n, m; int f[N][N]; int main() { 
    cin >> n >> m; memset(f, INF, sizeof f); f[0][0] = 0; for(int i = 1;i <= n;i ++) { 
    int v, w; cin >> v >> w; for(int j = 0;j <= m;j ++) { 
    f[i][j] = min(f[i - 1][j], f[i][max(0, j - v)] + w);//即使物品体积比j大，j - v < 0，也能选，等价于f[i - 1][0] } } cout << f[n][m] << endl; return 0; }

一维code

#include <iostream> #include <cstring> using namespace std; const int N = 110, INF = 0x3f3f3f3f; int n, m; int f[N]; int main() { 
    cin >> n >> m; memset(f, INF, sizeof f); f[0] = 0; for(int i = 1;i <= n;i ++) { 
    int v, w; cin >> v >> w; for(int j = m;j >= 0;j --) { 
    f[j] = min(f[j], f[max(0, j - v)] + w);//即使物品体积比j大，j - v < 0，也能选，等价于f[0] } } cout << f[m] << endl; return 0; }
今天的文章 背包问题至多，至少，恰好问题的研究分享到此就结束了，感谢您的阅读。
编程小号
上一篇 2025-01-04 23:06
下一篇 2025-01-04 23:01

相关推荐

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/101315.html