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

关于多重背包的笔记

多重背包可以看作01背包的拓展, 01背包是选或者不选。多重背包是选0个一直到选s个。

for (int i = 1; i <= n; ++i)
{for (int j = m; j >= w[i]; --j){f[j] = max(f[j], f[j - 1*w[i]] + 1*v[i], f[j - 2*w[i]] + 2*v[i],...f[j - s*w[i]] + s*v[i]);}
}

 由上述伪代码可以得知,要实现的多重背包只需要多加一层循环就可以了。

所得的f[m]就是最大价值。

 

//多重背包
#include<iostream>
using namespace std;
const int N = 110;
int f[N], n, m;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; ++i){int w, v, s; cin >> w >> v >> s;//重量,体积,数量for (int j = m; j >= w; --j){for (int k = 1; k <= s && k * w <= j; ++k){f[j] = max(f[j], f[j - k * w] + k * v);}}}cout << f[m] << '\n';return 0;
}

上述代码中就是套了一个01背包代码的框架,第三层循环中的 && k * w <= j可以减少不必要的步骤,优化时间。这种方法的时间复杂度为O(n^3),当数据过大的时候时间就会超限。所以接下来有一种求解数据大一些的求解多重背包的算法(多重背包的二进制优化)。

二进制优化的思想是将s个物品分解为log2(s)份,每份都是2的整次的这个个数。然后问题就会变成01背包问题。

 

//多重背包2
//二进制优化
#include<iostream>
#include<vector>
using namespace std;
const int N = 2e3 + 9;
int f[N], n, m;struct Good
{int v, w;
};int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);vector<Good> goods;cin >> n >> m;for (int i = 1; i <= n; ++i){int v, w, s; cin >> v >> w >> s;//将物品分解成log2(s)份//例如将至少使用log2(7)上取整个数来表示0到7这些数字//也就是2^0 2^1 2^2 (1 2 4)//0:都不选//1:只选1// ....//7:都选//若该数字的值不是2的次方-1,例如10,则有log2(10),也就是4个//(1 2 4 8),但是这样连不需要表示的11到15都可以表示出来,所以需要用10-1-2-4//3 - 8 < 0,所以分解为 1 2 4 3for (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 g : goods){for (int j = m; j >= g.v; --j){f[j] = max(f[j], f[j - g.v] + g.w);}}cout << f[m];return 0;
}

重点:01背包是n个物品每样一个 所以一共是n*1个物品 这里是n个物品每样最多s[i]个 所以总共最多是Σs[i]个, 把每一组的摊开变成一个一个 再进行01背包。也就是上述代码中的注释的选和不选。

 二进制优化参考:AcWing 5. 二进制优化,它为什么正确,为什么合理,凭什么可以这样分?? - AcWing

相关文章:

关于多重背包的笔记

多重背包可以看作01背包的拓展&#xff0c; 01背包是选或者不选。多重背包是选0个一直到选s个。 for (int i 1; i < n; i) {for (int j m; j > w[i]; --j){f[j] max(f[j], f[j - 1*w[i]] 1*v[i], f[j - 2*w[i]] 2*v[i],...f[j - s*w[i]] s*v[i]);} } 由上述伪代码…...

如何使用 Java 的反射

如何使用 Java 的反射&#xff1f; 通过一个全限类名创建一个对象 Class.forName(“全限类名”); 例如&#xff1a;com.mysql.jdbc.Driver Driver 类已经被加载到 jvm 中&#xff0c;并且完成了类的初始化工作就行了 类名.class; 获取 Class<&#xff1f;> clz 对象对…...

PLC-Recorder V3 修改服务器和客户端通讯端口的方法

PLC-Recorder V3是服务器和客户端的架构&#xff0c;他们之间用TCP通讯。如果客户端无法与服务器建立连接&#xff08;重启也无效&#xff0c;并且确保没有老版本的PLC-Recorder在运行&#xff09;&#xff0c;则可能是端口被占用了。这时候需要修改他们之间的通讯端口&#xf…...

libevent服务GET/POST的简单使用

目录 1、前言2、测试demo2.1、目录结构2.2、 测试源码2.2.1、http_server.cpp2.2.2、 http_server.h 2.3、 编译2.4、 运行结果2.4.1、测试POST2.4.2 、测试GET请求 1、前言 项目开发中经常需要使用到私有协议和Qt,Android等GUI前端通信&#xff0c;比较常用的使用POST和GET方式…...

MySQL 系列:注意 ORDER 和 LIMIT 联合使用的陷阱

文章目录 前言背后的原因ORDER BY 排序列存在相同值时返回顺序是不固定的LIMIT 和 ORDER BY 联合使用时的行为ORDER BY 或 GROUP BY 和 LIMIT 联合使用优化器默认使用有序索引 如何解决其它说明个人简介 前言 不知道大家在在分页查询中有没有遇到过这个问题&#xff0c;分页查…...

通过实例理解OAuth2授权

在之前的《通过实例理解Go Web身份认证的几种方式[1]》和《通过实例理解Web应用授权的几种方式[2]》两篇文章中&#xff0c;我们对Web应用身份认证(AuthN)和授权(AuthZ)的几种方式做了介绍并配以实例增强理解。 在现实世界中&#xff0c;还有一大类的认证与授权是在前面的文章中…...

MATLAB2022安装下载教程

安装包需从夸克网盘自取&#xff1a; 链接&#xff1a;https://pan.quark.cn/s/373ffc9213a1 提取码&#xff1a;N7PW 1.将安装包解压 2.以管理员的身份运行文件夹中的setup文件 3.点击高级选项--->我有文件安装密钥 4. 选择【是】&#xff0c;进入下一步 5.输入密钥 0532…...

从零开始搭建Go语言开发环境

https://www.liwenzhou.com/posts/Go/install_go_dev/ “go 命令现在默认在模块感知模式下构建包&#xff0c;即使没有 go.mod 存在也是如此。 “您可以将 GO111MODULE 设置为 auto&#xff0c;仅当当前目录或任何父目录中存在 go.mod 文件时&#xff0c;才能启用模块感知模式…...

vite+vue3+ts+tsx+ant-design-vue项目框架搭建

参与公司项目开发一段时间了&#xff0c;项目用到了很多新的技术&#xff08;vite,vue3,ts等等&#xff09;&#xff0c;但是框架都是别人搭好的&#xff0c;然后就想说如果是自己的话&#xff0c;会从零搭建一个吗&#xff0c;于是就有了这篇文章。 目录 一、涉及到的相关依…...

【5G PHY】5G小区类型、小区组和小区节点的概念介绍

博主未授权任何人或组织机构转载博主任何原创文章&#xff0c;感谢各位对原创的支持&#xff01; 博主链接 本人就职于国际知名终端厂商&#xff0c;负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作&#xff0c;目前牵头6G算力网络技术标准研究。 博客…...

创建个人网站(一)从零开始配置环境,搭建项目

目录 前言配置环境前端后端遇到的问题1.安装了nvm和node&#xff0c;vscode没反应2.安装完脚手架之后vue指令不存在 vscode插件&#xff08;以后遇到好的会添进去&#xff09; 前言 从刚开始学前端的html直到现在前后端都有在开发&#xff0c;我一直都有一个想法&#xff0c;就…...

fripside - promise lrc

[ti:promise] [ed:2] [rt:20] [ml:0|0] [00:05.172]words:Satoshi Yaginuma, Shinichiro Yamashita [00:09.664]music&arrangement:Satoshi Yaginuma, Shigetoshi Yamada [00:14.565]PCゲーム「ENGAGE LINKS」 (Alcot) エンディングテーマ [00:20.000] [00:46.442]朝の陽射…...

网络连接和协议

网络连接是通过一系列协议来实现的&#xff0c;其中TCP/IP协议和HTTP协议是其中两个关键的协议。 1. **TCP/IP协议&#xff1a;** - TCP/IP&#xff08;Transmission Control Protocol/Internet Protocol&#xff09;是一组用于在互联网上传输数据的协议。它是一个层次化的…...

MySQL数据库,表的增量备份与恢复

1. 从物理与逻辑的角度 数据库备份可以分为物理备份和逻辑备份。物理备份是对数据库操作系统的物理文件&#xff08;如数据 文件&#xff0c;日志文件等&#xff09;的备份。这种类型的备份适用于在出现问题时需要快速恢复的大型重要数据库。 物理备份又可以分为冷备份&#xf…...

13.Spring 整合 Kafka + 发送系统通知 + 显示系统通知

目录 1.Spring 整合 Kafka 2.发送系统通知 2.1 封装事件对象 2.2 开发事件的生产者和消费者 2.3 触发事件&#xff1a;在评论、点赞、关注后通知​编辑 3.显示系统通知 3.1 通知列表 3.1.1 数据访问层 3.1.2 业务层 3.1.3 表现层 3.2 开发通知详情 3.2.1 开发数据…...

windows 服务器 怎么部署python 程序

一、要在 Windows 服务器上部署 Python 程序&#xff0c;您需要遵循以下步骤&#xff1a; 安装 Python&#xff1a;首先&#xff0c;在 Windows 服务器上安装 Python。您可以从官方网站&#xff08;https://www.python.org/downloads/windows/&#xff09;下载最新的 Python 安…...

Chapter 7 - 2. Congestion Management in Ethernet Storage Networks以太网存储网络的拥塞管理

Location of Ingress No-Drop Queues入口无损队列的位置 Ingress queues for no-drop traffic are maintained by all the ports in a lossless Ethernet network. For the sake of simplicity, Figure 7-1 shows ingress no-drop queue(s) only at one location, but in real…...

深入理解前端项目中的 package.json

在前端开发中&#xff0c;package.json 是一个很重要的文件&#xff0c;它在Node.js和前端项目中扮演着重要的角色。这个文件用于存储项目的元数据以及管理项目的依赖关系。 package.json 文件是每个Node.js项目和许多前端项目的核心。它不仅定义了项目的基本属性&#xff0c;…...

4-Docker命令之docker build

1.docker build介绍 docker build命令是用来使用Dockerfile文件创建镜像 2.docker build用法 docker build [参数] PATH | URL | - [root@centos79 ~]# docker build --helpUsage: docker buildx build [OPTIONS] PATH | URL | -Start a buildAliases:docker buildx build…...

Hdfs java API

1.在主机上启动hadoop sbin/start-all.sh 这里有一个小窍门&#xff0c;可以在本机上打开8088端口查看三台机器的连接状态&#xff0c;以及可以打开50070端口&#xff0c;查看hdfs文件状况。以我的主虚拟机为例&#xff0c;ip地址为192.168.198.200&#xff0c;所以可以采用下…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章

用 Rust 重写 Linux 内核模块实战&#xff1a;迈向安全内核的新篇章 ​​摘要&#xff1a;​​ 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言&#xff0c;受限于 C 语言本身的内存安全和并发安全问题&#xff0c;开发复杂模块极易引入难以…...

boost::filesystem::path文件路径使用详解和示例

boost::filesystem::path 是 Boost 库中用于跨平台操作文件路径的类&#xff0c;封装了路径的拼接、分割、提取、判断等常用功能。下面是对它的使用详解&#xff0c;包括常用接口与完整示例。 1. 引入头文件与命名空间 #include <boost/filesystem.hpp> namespace fs b…...

Canal环境搭建并实现和ES数据同步

作者&#xff1a;田超凡 日期&#xff1a;2025年6月7日 Canal安装&#xff0c;启动端口11111、8082&#xff1a; 安装canal-deployer服务端&#xff1a; https://github.com/alibaba/canal/releases/1.1.7/canal.deployer-1.1.7.tar.gz cd /opt/homebrew/etc mkdir canal…...

ffmpeg(三):处理原始数据命令

FFmpeg 可以直接处理原始音频和视频数据&#xff08;Raw PCM、YUV 等&#xff09;&#xff0c;常见场景包括&#xff1a; 将原始 YUV 图像编码为 H.264 视频将 PCM 音频编码为 AAC 或 MP3对原始音视频数据进行封装&#xff08;如封装为 MP4、TS&#xff09; 处理原始 YUV 视频…...