当前位置： 首页 > news >正文

01背包和完全背包

news 2025/5/13 6:14:55

一、介绍

背包问题就是在一堆物品中选出一些来满足题目要求。

通过物品可以分成以下背包问题：

01 背包问题每种物品只能选或不选（选 0 次或 1 次）
完全背包问题每种物品可以选择⽆限次
多重背包问题每种物品有数量限制
分组背包问题物品被分为若⼲组，每组只能选⼀个物品
混合背包以上四种背包问题混在⼀起
多维费⽤的背包问题限定条件不⽌有体积，还会有其他因素（⽐如重量）

通过题目要求可以分成以下问题：方案总数，最优方案，方案可行性，具体方案...

二、01背包

最基本的问题要素：物品只有一个，不超过最大容量的方案？刚好等于最大容量的方案？

例题：01背包

登录—专业IT笔试面试备考平台_牛客网

1、不超过最大容量的方案

分析：

dp1[i][j]表示在[1, i]中选物品，体积不超过j的最大价值
不选i：dp1[i][j] = dp1[i - 1][j];
选i && j >= v[i]：dp1[i][j] = w[i] + dp1[i - 1][j - v[i]];
顺序：从1到i，从0到j
初始化：i等于0代表没有物品给我选，体积也一定不会超过j，所以dp1[0][j] = 0;

int main()
{int n, V;cin >> n >> V;for(int i = 1; i <= n; i++)cin >> v[i] >> w[i];vector<vector<int>> dp1(n + 1, vector<int>(V + 1));for(int i = 1; i <= n; i++){for(int j = 0; j <= V; j++){dp1[i][j] = dp1[i - 1][j];if(j - v[i] >= 0)dp1[i][j] = max(dp1[i][j], w[i] + dp1[i - 1][j - v[i]]);}}cout << dp1[n][V] << endl;return 0;
}

2、刚好等于最大容量的方案

分析：

dp2[i][j]表示在[1, i]中选物品，体积刚好等于j时的最大价值
不选i：dp2[i][j] = dp2[i - 1][j];
选i && j >= v[i]：dp2[i][j] = w[i] + dp2[i - 1][j - v[i]];
顺序：从1到i，从0到j
初始化：i等于0代表没有物品给我选，那dp2[0][0] = 0; 但是j大于0的时候位置是不合法的，应该是负无穷，直接代入公式负无穷即使加了w[i]也是负数没有意义，只要在最后判断以下是不是负数就行

int main()
{int n, V;cin >> n >> V;for(int i = 1; i <= n; i++)cin >> v[i] >> w[i];vector<vector<int>> dp2(n + 1, vector<int>(V + 1, -INF));dp2[0][0] = 0;for(int i = 1; i <= n; i++){for(int j = 0; j <= V; j++){dp2[i][j] = dp2[i - 1][j];if(j - v[i] >= 0)dp2[i][j] = max(dp2[i][j], w[i] + dp2[i - 1][j - v[i]]);}}dp2[n][V] = max(dp2[n][V], 0);cout << dp2[n][V];return 0;
}

3、空间优化

每次更新只依赖于上一层的dp表，所以用滚动数组
注意这一层的更新用的是j - v[i]，即左上方的值
所以这一层的更新是从右向左
做法：删去i维，遍历顺序改变

int main()
{int n, V;cin >> n >> V;for(int i = 1; i <= n; i++)cin >> v[i] >> w[i];
//     vector<vector<int>> dp1(n + 1, vector<int>(V + 1));
//     vector<vector<int>> dp2(n + 1, vector<int>(V + 1, -INF));vector<int> dp1(V + 1);vector<int> dp2(V + 1, -INF);
//     dp2[0][0] = 0;dp2[0] = 0;for(int i = 1; i <= n; i++){for(int j = V; j - v[i] >= 0; j--){
//             dp1[j] = dp1[j];
//             if(j - v[i] >= 0)dp1[j] = max(dp1[j], w[i] + dp1[j - v[i]]);//             dp2[j] = dp2[j];
//             if(j - v[i] >= 0)dp2[j] = max(dp2[j], w[i] + dp2[j - v[i]]);}}cout << dp1[V] << endl;dp2[V] = max(dp2[V], 0);cout << dp2[V];return 0;
}

三、完全背包

最基本的问题要素：物品有无限个，不超过最大容量的方案？刚好等于最大容量的方案？

例题：完全背包

登录—专业IT笔试面试备考平台_牛客网

1、不超过最大容量的方案

分析：

dp1[i][j]表示在[1, i]物品中选，体积不超过j的最大价值
不选i：dp1[i][j] = dp1[i - 1][j];
选i && j >= v[i]：dp1[i][j] = dp1[i][j - v[i]] + w[i];
理解选i的更新逻辑：由于物品个数是无限的，所以即使这一次操作拿出了i物品。也仅仅只能改变背包容量，不代表要像01背包一样只能在[1, i - 1]里面选了，又因为j是从左向右遍历的，j - v[i] < j
所以可以看作是用更新之后的dp[i][j - v[i]]来更新dp[i][j]，已经包含了尽可能多个数的i物品，所以逻辑正确
初始化：逻辑和01背包一样

int main()
{int n, V;cin >> n >> V;vector<vector<int>> dp1(n + 1, vector<int>(V + 1));for(int i = 1; i <= n; i++)cin >> v[i] >> w[i];for(int i = 1; i <= n; i++){for(int j = 0; j <= V; j++){dp1[i][j] = dp1[i - 1][j];if(j - v[i] >= 0)dp1[i][j] = max(dp1[i][j], dp1[i][j - v[i]] + w[i]);}}cout << dp1[n][V] << endl;return 0;
}

2、刚好等于最大容量的方案

分析：

dp2[i][j]表示在[1, i]物品中选，体积等于j的最大价值
不选i：dp2[i][j] = dp2[i - 1][j];
选i && j >= v[i]：dp2[i][j] = dp2[i][j - v[i]] + w[i];
初始化：逻辑和01背包一样

int main()
{int n, V;cin >> n >> V;vector<vector<int>> dp2(n + 1, vector<int>(V + 1, -INF));dp2[0][0] = 0;for(int i = 1; i <= n; i++)cin >> v[i] >> w[i];for(int i = 1; i <= n; i++){for(int j = 0; j <= V; j++){dp2[i][j] = dp2[i - 1][j];if(j - v[i] >= 0)dp2[i][j] = max(dp2[i][j], dp2[i][j - v[i]] + w[i]);}}dp2[n][V] = max(dp2[n][V], 0);cout << dp2[n][V] << endl;return 0;
}

3、空间优化

用到了同一行和上一行的左上数据，所以是从左向右

int main()
{int n, V;cin >> n >> V;
//     vector<vector<int>> dp1(n + 1, vector<int>(V + 1));
//     vector<vector<int>> dp2(n + 1, vector<int>(V + 1, -INF));vector<int> dp1(V + 1);vector<int> dp2(V + 1, -INF);dp2[0] = 0;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 <= V; j++){
//             dp1[i][j] = dp1[i - 1][j];
//             if(j - v[i] >= 0)dp1[j] = max(dp1[j], dp1[j - v[i]] + w[i]);//             dp2[i][j] = dp2[i - 1][j];
//             if(j - v[i] >= 0)dp2[j] = max(dp2[j], dp2[j - v[i]] + w[i]);}}cout << dp1[V] << endl;dp2[V] = max(dp2[V], 0);cout << dp2[V] << endl;return 0;
}

四、例题

1、采药

P1048 [NOIP 2005 普及组] 采药 - 洛谷

// https://www.luogu.com.cn/problem/P1048
#include <bits/stdc++.h>
using namespace std;int T, M;
int t[110];
int w[110];// dp[i][j]表示在[1, i]中选，时间不超过j的最大价值
int main()
{cin >> T >> M;for(int i = 1; i <= M; i++)cin >> t[i] >> w[i];vector<vector<int>> dp(M + 1, vector<int>(T + 1));for(int i = 1; i <= M; i++){for(int j = 0; j <= T; j++){dp[i][j] = dp[i - 1][j];if(j - t[i] >= 0)dp[i][j] = max(dp[i][j], dp[i - 1][j - t[i]] + w[i]);}}cout << dp[M][T];return 0;
}

2、小A点菜

P1164 小A点菜 - 洛谷

// https://www.luogu.com.cn/problem/P1164
#include <bits/stdc++.h>
using namespace std;int M, N;
int a[110];
const int INF = 0x3f3f3f3f;
// dp[i][j]表示在[1, i]中选，正好花j元的方案个数
// 不选：dp[i][j] = dp[i - 1][j];
// 选 && j - a[i] >= 0：dp[i][j] += dp[i - 1][j - a[i]];
// 初始化：dp[0][0] = 1; 其余dp[0][j] = 0;
int main()
{cin >> N >> M;for(int i = 1; i <= N; i++)cin >> a[i];vector<vector<int>> dp(N + 1, vector<int>(M + 1));dp[0][0] = 1;for(int i = 1; i <= N; i++){for(int j = 0; j <= M; j++){dp[i][j] = dp[i - 1][j];if(j - a[i] >= 0)dp[i][j] += dp[i - 1][j - a[i]];}}cout << dp[N][M];return 0;
}

3、Cow Frisbee Team S

P2946 [USACO09MAR] Cow Frisbee Team S - 洛谷

// https://www.luogu.com.cn/problem/P2946
#include <bits/stdc++.h>
using namespace std;
int n, f;
int a[2010];
const int mod = 1e8;
int dp[2010][1010];// dp[i][j]表示在[1, i]中选，能力值总和模f之后的j的方案数
// 由模数的性质得答案直接累加在dp[n][0]，又因为没有0这个能力值，再减去dp[0][0]的1
// 不选：dp[i][j] = dp[i - 1][j];
// 选：dp[i][j] += dp[i - 1][j - a[i] % f];
// 此时j - a[i] % f < 0是有意义的，虽然数据是负数，但是数据是取模过的，所以不能保证一定是正数，当为负数的时候要做的是把j - a[i] % f这个负数变成原来的正数，即f = 5, -2->3，操作是模加模，(((j - a[i] % f) % f) + f) % fint main()
{cin >> n >> f;for(int i = 1; i <= n; i++)cin >> a[i];dp[0][0] = 1;for(int i = 1; i <= n; i++){for(int j = 0; j <= f; j++){dp[i][j] = dp[i - 1][j];int x = (((j - a[i] % f) % f) + f) % f;dp[i][j] = (dp[i][j] + dp[i - 1][x]) % mod;}}cout << dp[n][0] - 1;return 0;
}

4、疯狂的采药

P1616 疯狂的采药 - 洛谷

// https://www.luogu.com.cn/problem/P1616
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int T, n;
int w[10010];
int t[10010];int main()
{cin >> T >> n;for(int i = 1; i <= n; i++)cin >> t[i] >> w[i];vector<ll> dp(T + 1);for(int i = 1; i <= n; i++){for(int j = t[i]; j <= T; j++){dp[j] = max(dp[j], dp[j - t[i]] + w[i]);}}cout << dp[T];return 0;
}

5、Buying Hay S

P2918 [USACO08NOV] Buying Hay S - 洛谷

// https://www.luogu.com.cn/problem/P2918
#include <bits/stdc++.h>
using namespace std;
int h, n;
int p[110];
int c[110];
const int INF = 0x3f3f3f3f;// dp[i][j]表示在[1, i]中选，采购了至少j的草料的最小开销
// 不选i: dp[i][j] = dp[i - 1][j];
// 选i: dp[i][j] = dp[i][j - p[i]] + c[i];
// 思考j - p[i]为负数表示公司草料很重，直接超过了预计的j，此时负数是符合题目要求的，所以要变成0
// 初始化：dp[0][0] = 0; 当i等于0，j大于0的时候一定不会采购到j，又因为取min，所以是正无穷
int main()
{cin >> n >> h;vector<vector<int>> dp(n + 1, vector<int>(h + 1, INF));dp[0][0] = 0;for(int i = 1; i <= n; i++)cin >> p[i] >> c[i];for(int i = 1; i <= n; i++){for(int j = 0; j <= h; j++){dp[i][j] = dp[i - 1][j];dp[i][j] = min(dp[i][max(0, j - p[i])] + c[i], dp[i][j]);}}cout << dp[n][h];return 0;
}

有很多时候题意会从 j - v[i] 的正负值下手

正数代表剩余容量大于等于0，即一般合法情况下的数据

负数代表加上物品i之后容量超过了j，这是引出第三个核心问题，至少等于最大容量？此时负数合法，但是应该用 j = 0 进行更新，所以此题是 max(0, j - v[i])

6、纪念品

P5662 [CSP-J2019] 纪念品 - 洛谷

// https://www.luogu.com.cn/problem/P5662
#include <bits/stdc++.h>
using namespace std;
int t, n, m;
int p[110][110];
int dp[110][10010];// 贪心：我要用昨天的利润当做今天的本金去投资明天 
// dp[i][j]表示在某天中[1, i]的物品中选，使用不超过j本金，用今天买明天卖的策略统计最大利润 
// 不买i：dp[i][j] = dp[i - 1][j];
// 买i：dp[i][j] = dp[i][j - p[t][i]] + (p[t + 1][i] - p[t][i]);void f(int t)
{memset(dp, 0, sizeof dp);for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){dp[i][j] = dp[i - 1][j];if(j - p[t][i] >= 0)dp[i][j] = max(dp[i][j], dp[i][j - p[t][i]] + p[t + 1][i] - p[t][i]);}}m += dp[n][m];
}int main()
{cin >> t >> n >> m;for(int i = 1; i <= t; i++)for(int j = 1; j <= n; j++)cin >> p[i][j];for(int i = 1; i < t; i++)f(i);cout << dp[n][m] + m;return 0;
}
http://www.xdnf.cn/news/405235.html

相关文章：

  • 基于Qt6 + MuPDF在 Arm IMX6ULL运行的PDF浏览器——MuPDF Tools
  • 大项目k8s集群有多大规模，多少节点，有多少pod
  • 智能指针入门：深入理解 C++ 的 shared_ptr
  • AI中的MCP是什么？MCP的作用及未来方向预测 (使用go-zero 快速搭建MCP服务器)
  • 2025年北京市积分落户申报
  • 经典案例 | 智能眼镜中瞳距调节和近视调节的应用
  • web 自动化之 Unittest 四大组件
  • 【NextPilot日志移植】ULog
  • 文档外发安全：企业数据防护的最后一道防线
  • RabbitMQ 工作模式
  • JWT的介绍与在Fastapi框架中的应用
  • 单片机-STM32部分：13-1、蜂鸣器
  • 常用依赖文件库
  • kubernetes服务自动伸缩-VPA
  • ESP32开发入门(九)：HTTP服务器开发实践
  • Day22打卡-复习
  • 【K8S学习之探针】详细了解就绪探针 readinessProbe 和存活探针 livenessProbe 的配置
  • Kotlin 异步初始化值
  • JVM类加载
  • 生产环境怎么移除console
  • WebSocket集成方案对比
  • 中华春节符号全球推广委员会——“金文形意书《易经》成果展”研学之旅
  • 【Spark】使用Spark集群搭建Yarn模式
  • Docker-配置私有仓库（Harbor）
  • mapreduce-wordcount程序2
  • PostgreSQL 中的序列（Sequence）
  • 力扣HOT100之二叉树：226. 翻转二叉树
  • WSL-Ubuntu 中安装 Git LFS 记录
  • 网络编程epoll和udp
  • 华为防火墙配置与网络协议实战指南：从基础到高阶排查