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

多重背包问题 一句话说清楚“二进制拆分“

目录

区别:

一句话说清楚:

板子:


区别:

得先懂完全背包问题完全背包问题 非零基础-CSDN博客

都是让背包内价值最大。

完全背包问题每种物品可以取无数次。而多重背包问题每件取的次数有限。

都可以用的最挫的方法就是0~k件去遍历。

完全背包问题可以推出公式优化(或者说逻辑上可以直接一次从前往后遍历)

多重背包问题不好推公式。本文讲的是二进制拆分方法来优化(完全背包问题也可以用这个,但是不是最优)

可以参考大佬文章学习 背包九讲——全篇详细理解与代码实现-CSDN博客

练习题: P1776 宝物筛选 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

一句话说清楚:

一句话说清这个二进制拆分:

int 整形知道吧?只需要32位就可以表示 -2147483647 - 1 ~ 2147483647

有点感觉吗?

再细说:1可以表示1 , 2可以表示2 , 1和2一起可以表示3 ,但我们只需要用到两个数,不需要遍历1到3

板子:

目的:把num拆成二进制  (最后一位(即剩余)未必是2的倍数)

第 i 件物品 ,本次装 k 件 ,j 是当前背包大小

W 是背包大小

m[ i ]是该物品的数目,w[ i ]是该物品的大小 , v[ i ]是该物品的价值

num是最大数目 : 看能装多少 W / w[i] ,再看有多少m[ i ] 。数目够,就尽可能装。数目w[i]不够,那就全装进去。

	vector<ll>dp(MAX);for (int i = 1; i <= n; i++){int num = min(m[i], W / w[i]);for (int k = 1; num > 0; k<<=1){if (k > num)k = num;num -= k;for (int j = W; j >= 0; j--){if (j - w[i] * k >= 0)dp[j] = max(dp[j], dp[j - w[i] * k] + v[i] * k);}}			}

if可以自行优化掉

ε≡٩(๑>₃<)۶ 一心向学,加油!

相关文章:

多重背包问题 一句话说清楚“二进制拆分“

目录 区别&#xff1a; 一句话说清楚&#xff1a; 板子&#xff1a; 区别&#xff1a; 得先懂完全背包问题完全背包问题 非零基础-CSDN博客 都是让背包内价值最大。 完全背包问题每种物品可以取无数次。而多重背包问题每件取的次数有限。 都可以用的最挫的方法就是0~k件去…...

nodejs微信小程序+python+PHP本科生优秀作业交流网站的设计与实现-计算机毕业设计推荐

通过软件的需求分析已经获得了系统的基本功能需求&#xff0c;根据需求&#xff0c;将本科生优秀作业交流网站功能模块主要分为管理员模块。管理员添加系统首页、个人中心、用户管理、作业分类管理、作业分享管理、论坛交流、投诉举报、系统管理等操作。 随着信息化社会的形成…...

使用git出现的问题

保证 首先保证自己的git已经下载 其次保证自己的gitee账号已经安装并且已经生成ssh公钥 保证自己要push的代码在要上传的文件夹内并且配置文件等都在父文件夹&#xff08;也就是文件没有套着文件&#xff09; 问题 1 $ git push origin master gitgitee.com: Permission de…...

rk3568 适配PCIE(二)

rk3568 适配pcie3.0 PCIe(Peripheral Component Interconnect Express)是一种用于连接计算机主板和其他设备的高速串行总线接口。PCIe 2.0和PCIe 3.0是两个不同版本的PCIe规范,它们在以下几个方面有所不同: 带宽:PCIe 2.0的理论带宽为每条通道5 Gbps,而PCIe 3.0的理论带…...

Java基础 进制

在Java中&#xff0c;可以使用不同的进制表示整数常量和字面量。 十进制&#xff08;Decimal&#xff09;&#xff1a;默认为十进制&#xff0c;不需要添加前缀。例如&#xff1a;int num 10;二进制&#xff08;Binary&#xff09;&#xff1a;以0b或0B作为前缀表示二进制。例…...

springboot中@Builder注解的详细用法实例,跟数据库结合。

在Spring Boot中&#xff0c;Builder注解是Lombok库提供的一个注解&#xff0c;用于生成带有Builder模式支持的构造器方法。通过Builder注解&#xff0c;可以简化对象的创建过程&#xff0c;特别适用于需要设置多个属性的情况。 下面是一个使用Builder注解的示例&#xff1a; …...

WT2605C蓝牙音频语音芯片:具备大功率IO驱动能力,引领音频技术新纪元

在当今的电子科技时代&#xff0c;功率强大的IO驱动能力成为音频设备性能的重要指标。近日&#xff0c;一款名为WT2605C的蓝牙音频语音芯片&#xff0c;以其最高可直接驱动64mA的大功率IO驱动能力&#xff0c;引起业界的广泛关注。这款芯片的出现&#xff0c;无疑将为音频设备的…...

【Java 基础】20 多线程操作方法

文章目录 1.获取和设置线程的名字1&#xff09;获取默认名字2&#xff09;获取自定义的名字 2.判断线程是否启动3.线程的强制执行4.让线程睡一会儿5.中断线程6.守护线程7.线程的礼让 前一节我们介绍了线程的定义、创建方法、状态以及各状态间的转换。在状态转换处只是简单的说明…...

SpringBoot使用mybatis-plus分页查询无效解决方案

问题概述 SpringBoot中使用mybatis-plus实现分页查询时&#xff0c;提供一个page分页对象和一个QueryWrapper条件类对象&#xff0c;在使用Service.page(page,queryWrapper)方法进行分页查询时&#xff0c;发现并未查询到分页的结果&#xff0c;反而是查询到全部符合条件的结果…...

QT 中 线程池 (备查)

QRunnable类 API 1&#xff09;在Qt中使用线程池需要先创建任务&#xff0c;添加到线程池中的每一个任务都需要是一个 QRunnable 类型&#xff0c;因此在程序中需要创建子类继承 QRunnable 这个类。 2&#xff09;然后重写 run() 方法&#xff0c;在这个函数中编写要在线程池中…...

LeetCode刷题笔记第71题:简化路径

LeetCode刷题笔记第71题&#xff1a;简化路径 题目 给定一个路径&#xff0c;简化路径 要求&#xff1a; 1、以’/‘开头 2、两个目录之间只有一个’/’ 3、不能以’/‘结尾 4、路径中不能有’.‘和’…’ 想法 利用栈的数据存储方式的思想&#xff0c;将路径字符顺序入栈遇…...

JavaScript <md5加密的两种不同输出结果分析>--案例(二点一)

前言: 问题是这样的,在浏览器中看到这段代码 然后在控制台进行输出.得到: 紧接着,就在,js文件里面进行转译: 可是,得到的结果是: 这是问题!!! 正题: 为什么相同的js代码,在 .js 文件中的输出与 Chrome 控制台中的输出不一样? 环境差异&#xff1a;不同的JavaScript环境&…...

『亚马逊云科技产品测评』活动征文|基于亚马逊EC2云服务器配置Nginx静态网页

授权声明&#xff1a;本篇文章授权活动官方亚马逊云科技文章转发、改写权&#xff0c;包括不限于在 Developer Centre, 知乎&#xff0c;自媒体平台&#xff0c;第三方开发者媒体等亚马逊云科技官方渠道 亚马逊EC2云服务器&#xff08;Elastic Compute Cloud&#xff09;是亚马…...

28、卷积 - 卷积的基础公式

本节推导一下卷积的基础公式,还是先上一张卷积运算的示意图图。 我们知道,一张图片有 3 个维度,分别是长、宽、通道。 这三个维度分别用 3 个字母代替,分别是 H(Height, 对应的是长这一维度), W(Width, 对应的是宽这一维度),C(Channel,对应的是通道这一维度)。 对于…...

Mac电脑vm虚拟机 VMware Fusion Pro中文 for mac

VMware Fusion Pro是一款功能强大的虚拟机软件&#xff0c;适用于需要在Mac电脑上运行其他操作系统的用户。它具有广泛的支持、快速稳定的特点以及多种高级功能&#xff0c;可以满足用户的各种需求和场景。 多操作系统支持&#xff1a;VMware Fusion Pro允许在Mac电脑上运行多…...

区块链技术的应用场景和优势

目录 一、引言 二、什么是区块链技术 三、区块链技术的应用场景 1.金融领域 &#xff08;1&#xff09;支付和清算&#xff1a;区块链可以为支付和金融结算提供更加快速、安全、便捷的方式。例如瑞士银行UBS和Deutsche Bank已经合作开发了基于区块链的支付和清算系统。 &a…...

java面试题-谈谈sql优化-mysql

远离八股文&#xff0c;面试大白话&#xff0c;通俗且易懂 看完后试着用自己的话复述出来。有问题请指出&#xff0c;有需要帮助理解的或者遇到的真实面试题不知道怎么总结的也请评论中写出来&#xff0c;大家一起解决。 这是面试总结出来的几点&#xff0c;每次问道都是这么回…...

【Linux服务器Java环境搭建】07 在linux中安装MySql,以及对MySQL的配置与远程连接

【Linux服务器Java环境搭建】01购买云服务器以及在服务器中安装Linux系统 【Linux服务器Java环境搭建】02 通过xftp和xshell远程连接云服务器 【Linux服务器Java环境搭建】03 Git工具安装 【Linux服务器Java环境搭建】04 JDK安装&#xff08;JAVA环境安装&#xff09; 【Linux服…...

用 LangChain 搭建基于 Notion 文档的 RAG 应用

如何通过语言模型查询 Notion 文档&#xff1f;LangChain 和 Milvus 缺一不可。 在整个过程中&#xff0c;我们会将 LangChain 作为框架&#xff0c;Milvus 作为相似性搜索引擎&#xff0c;用二者搭建一个基本的检索增强生成&#xff08;RAG&#xff09;应用。在之前的文章中&a…...

QT中如何使用自定义控件

在 Qt 中&#xff0c;要使用自定义控件&#xff0c;需要遵循以下步骤&#xff1a; 创建自定义控件&#xff1a; 首先&#xff0c;需要创建一个自定义控件类&#xff0c;该类继承自 QWidget 或 QGraphicsItem 等基本控件类&#xff0c;并实现其相关函数和槽函数等。 在头文件中…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

node.js的初步学习

那什么是node.js呢&#xff1f; 和JavaScript又是什么关系呢&#xff1f; node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说&#xff0c; 需要在node.js的环境上进行当JavaScript作为前端开发语言来说&#xff0c;需要在浏览器的环境上进行 Node.js 可…...