当前位置: 首页 > 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;所以可以采用下…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...