背包问题的模板及各个等价变形

目录

0-1背包 —— 二维二重循环

01背包 —— 一维二重循环

完全背包 —— 二维三重循环

完全背包 —— 二维二重循环

完全背包 —— 一维二重循环

0-1背包 —— 二维二重循环

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

01背包 —— 一维二重循环

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

完全背包 —— 二维三重循环

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int dp[N][N];
int v[N], w[N];int main() {int n, vm;cin >> n >> vm;for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i];}for(int i = 1; i <= n; i++){for(int j = 1; j <= vm; j++){for(int k = 0; k * v[i] <= j; k++) //从不选到多选{dp[i][j] = max(dp[i][j], dp[i-1][j - k*v[i]] + k*w[i]);}}}cout << dp[n][vm];return 0;
}

这个就是比选0,选1多了选的情况。

多选多少,由j是v[i]的多少倍决定。

下拉操作(就是选0)整合进了k = 0的情况。

为什么不是dp[i][j] = dp[i-1][j] ?

因为现在可能有多个值来更新dp[i][j],max函数只接受两个参数,于是不断更新dp[i][j]自身,而dp[i-1][j]代表的是选0,已经被整合进dp[i-1][j - k*v[i]] + k*w[i] 的众多分身了(k=0时的分身)

完全背包 —— 二维二重循环

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

把第一个蓝色等式两边进行替换,把j替换为j - v[i]。得到第二个蓝色等式,对第一个蓝色式子右边的局部进行替换得到红色等式。

完全背包 —— 一维二重循环

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int dp[N];
int v[N], w[N];int main() {int n, vm;cin >> n >> vm;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 <= vm; j++){dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}cout << dp[vm];return 0;
}

类似0-1背包的降维操作。但是这里j参数下的值的求取不依赖于上层的更小的j参数下的值的求取,而是本层的,因此正常从小到大遍历即可。

下图示例

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/404287.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

鸿蒙内核源码分析——(自旋锁篇)

本篇说清楚自旋锁 读本篇之前建议先读系列篇 进程/线程篇. 内核中哪些地方会用到自旋锁?看图: 概述 自旋锁顾名思义&#xff0c;是一把自动旋转的锁&#xff0c;这很像厕所里的锁&#xff0c;进入前标记是绿色可用的&#xff0c;进入格子间后&#xff0c;手一带&#xff0c…

Github 2024-08-19 开源项目周报Top15

根据Github Trendings的统计,本周(2024-08-19统计)共有15个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Python项目7JavaScript项目3TypeScript项目3Dart项目2HTML项目1PowerShell项目1Clojure项目1C++项目1Rust项目1Bootstrap 5: Web上开发响应式、…

嵌入式软件--模电基础 DAY 2

强电和弱电&#xff0c;简单一点是以电死人为标准的&#xff0c;交流电36伏特以下&#xff0c;直流电24V以下&#xff0c;为安全电压&#xff0c;是为弱电&#xff0c;反则强电。 市电进入家庭&#xff0c;连接你的电脑&#xff0c;220V的电压为什么没有让你感到危险&#xff…

YOLO知识点总结:

分类&#xff1a; 即是将图像结构化为某一类别的信息&#xff0c;用事先确定好的类别(category)或实例ID来描述图片。这一任务是最简单、最基础的图像理解任务&#xff0c;也是深度学习模型最先取得突破和实现大规模应用的任务。其中&#xff0c;ImageNet是最权威的评测集&…

【区块链+金融服务】基于区块链的一站式绿色金融开放平台 | FISCO BCOS应用案例

科技的进步为绿色金融发展提供了新的机遇&#xff0c;但银行、企业、第三方金融机构等在进行绿色金融业务操作过程中&#xff0c; 存在着相关系统和服务平台建设成本高、迭代难度大、数据交互弱、适配难等痛点。 基于此&#xff0c;中碳绿信采用国产开源联盟链底层平台 FISCO …

【Android 远程数据库操作】

按正常情况下&#xff0c;前端不应该直接进行远程数据库操作&#xff0c;这不是一个明智的方式&#xff0c;应该是后端提供对应接口来处理&#xff0c;奈何公司各方面原因需要前端这样做。 对此&#xff0c;我对远程数据库操作做了总结&#xff0c;便于自己复盘&#xff0c;同…

【Qt】常用控件QCheckBox

常用控件QCheckBox QCheckBox表示复选按钮&#xff0c;可以允许选中多个。 QCheckBox继承自QAbstractButton 例子&#xff1a;获取复选按钮的取值 使用Qt Designer先大体进行设计 代码实现&#xff1a; #include "widget.h" #include "ui_widget.h"Widge…

【网络】套接字(socket)编程——TCP版

接着上一篇文章&#xff1a;http://t.csdnimg.cn/GZDlI 在上一篇文章中&#xff0c;我们实现的是UDP协议的&#xff0c;今天我们就要来实现一下TCP版本的 接下来接下来实现一批基于 TCP 协议的网络程序&#xff0c;本节只介绍基于IPv4的socket网络编程 基于 TCP 的网络编程开…

【leetcode详解】T3137(思路详解 代码优化感悟)

思路详解 要解决这个问题&#xff0c;我们的大致思路是这样&#xff1a;找到长度为k的字符串 (记为stringA) &#xff0c;统计重复次数最多的那一个&#xff0c;则最终对应的k周期字符串就是 [stringA * n] 的形式( n word.length() / k&#xff09; 要实现多对象的计数&…

iOS 18.1 Beta 2评测:新变化与体验升级

苹果公司近日向开发者推送了iOS 18.1 Beta 2更新&#xff0c;这一版本基于beta1版本进行多个方面优化和改进&#xff0c;为用户带来了更加流畅和个性化的使用体验。作为一位热衷于体验新系统的用户&#xff0c;小编也是第一时间升级了Beta 2版本&#xff0c;并对其进行了全面的…

51 无显式主键时 mysql 增加的 DB_ROW_ID

前言 这里主要是 探讨, 在我们创建了一个 无主键的数据表, 然后 mysql 会为我们增加的这一个 DB_ROW_ID 的相关 新建一个无主键字段的数据表如下 CREATE TABLE implicit_id_table (username varchar(16) DEFAULT NULL,age int(11) DEFAULT NULL ) ENGINEInnoDB DEFAULT CH…

Docker 部署loki日志 用于微服务

因为每次去查看日志都去登录服务器去查询相关日志文件&#xff0c;还有不同的微服务&#xff0c;不同日期的文件夹&#xff0c;超级麻烦&#xff0c;因为之前用过ELK&#xff0c;原本打算用ELK&#xff0c;在做技术调研的时候发现了一个轻量级的日志系统Loki&#xff0c;果断采…

如何一键删除iPhone相册所有照片

拍照已成为我们记录日常生活的常态。但是&#xff0c;大量照片便会积累在设备上&#xff0c;这不仅占用了大量存储空间&#xff0c;而且随着时间的推移&#xff0c;管理这些照片也变得越来越困难。如果你决定清理旧照片&#xff0c;或者出于隐私考虑需要删除所有照片&#xff0…

【数据结构】链式结构实现:二叉树

二叉树 一.快速创建一颗二叉树二.二叉树的遍历1.前序、中序、后序遍历&#xff08;深度优先遍历DFS&#xff09;2.层序遍历&#xff08;广度优先遍历BFS&#xff09; 三.二叉树节点的个数四.二叉树叶子节点的个数五.二叉树的高度六.二叉树第k层节点个数七.二叉树查找值为x的节点…

什么是机器人快换盘?

机器人快换盘&#xff0c;行业内也称作工具快换盘、换枪盘、快换工具盘、快速更换器、快换器、 快换夹具、治具快换等。是末端执行器快速更换装置&#xff08;End-Of-Arm Tooling&#xff0c;简称EOAT&#xff09;&#xff0c;是工业自动化领域中用于机器人手臂上的一种重要设备…

MiniCPM-V: A GPT-4V Level MLLM on Your Phone论文阅读

大模型的趋势&#xff1a;模型性能越来越好&#xff0c;模型参数变小&#xff0c;端边设备计算能力变强。 MiniCPM-V优点 结果好、OCR能力突出、多分辨率、多语言、易于部署 模型结构 图片encoder适用vit。输入整体以及切片。切片使用自适应算法&#xff0c;通过计算分数&am…

人机环境系统智能已经超越了传统的空间智能和物理世界的概念

人机环境系统智能已经超越了传统的空间智能和物理世界的概念&#xff0c;进入了更为复杂的层次。在人机环境系统中&#xff0c;智能不仅涉及对物理世界的感知和理解&#xff0c;还包括对人类语言、情感、意图等的理解和生成。人工智能技术的应用&#xff0c;如自然语言处理、机…

C++静态数组的用法

每日诗词&#xff1a; 疏影横斜水清浅&#xff0c;暗香浮动月黄昏。 ——《山园小梅其一》林逋 目录 数组的基础操作&#xff1a; 数组元素的增加&#xff1a; 演示&#xff1a; 数组元素的删除&#xff1a; 演示&#xff1a; 数组元素的访问和修改&#xff1a; 演示&am…

WLAN射频调优

射频调优的基本原则 信道优化的基本原则 2.4G射频在非高密部署场景中推荐采用1、6、11这种3个不重叠的信道进行规划&#xff0c;同理也可以选用2、7、12或3、8、13的组合方式&#xff1b;在高密部署场景中则推荐采用1、5、9、13共4个信道组合进行规划。5G射频推荐采用36、40、…

HQChart使用教程101-创建内置键盘精灵

HQChart使用教程101-创建内置键盘精灵 键盘精灵步骤1. 创建键盘精灵实例2. 设置事件回调3. 初始化键盘精灵4. 设置码表数据5. 监听"keydown","mousedown" 交流QQ群HQChart代码地址键盘精灵源码 完整实例 键盘精灵 键盘精灵是一种便捷操作软件的功能工具&a…