多重背包问题中的二进制状态压缩
1.多重背包问题

经典的多重背包问题和01背包问题的相似之处在于二者的一维遍历顺序都是从右侧往左侧遍历。
同时多重背包的一维写法不比二维写法降低时间复杂度。
2.多重背包标准写法:(平铺展开形式)
class Solution {public int maxValue(int N, int C, int[] s, int[] v, int[] w) {int[] dp = new int[C + 1];for (int i = 0; i < N; i++) {for (int j = C; j >= v[i]; j--) {for (int k = 0; k <= s[i] && j >= k * v[i]; k++) {dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]);}}}return dp[C];}
}
因为转换为一维之后,无法记录每个物品的使用次数,所以多重背包的一维写法并不能减低时间复杂度,注意完全版背包的一维写法是能够降低时间复杂度的。此处的代码与01背包十分相似。01背包的代码如下:
class Solution {public int maxValue(int N, int C, int[] v, int[] w) {int[] dp = new int[C + 1];for (int i = 0; i < N; i++) {for (int j = C; j >= v[i]; j--) {// 不选该物品int n = dp[j]; // 选择该物品int y = dp[j-v[i]] + w[i]; dp[j] = Math.max(n, y);}}return dp[C];}
}
3.二进制压缩形式的多重背包
上述的多重背包的解法实际上是将带选择的m个物品平着展开为[1,1,1....](共计m个),具体可以查看最后一个for循环的写法,不断尝试一个一个的将数据加进去。
实际上这种解法只能解决数据量为平方级别的数据。而二进制解法则是将原本为 n 的物品用 ceil(log(n)) 个数来代替,从而降低算法复杂度。
学过 Linux 的都知道文件权限最高是 7,代表拥有读、写、执行的权限,但其实这个 7 是对应了 1、2、4 三个数字的,也就是 r:1、w:2、x:4 ,三种权限的组合共有 8 种可能性
7 可以用 1、2、4 来代替,像刚刚提到的 10 ,我们可以使用 1、2、4、3 来代替,你可能会有疑问,为什么是 1、2、4、3,而不是 1、2、4、6 或者 1、2、4、8 呢?
其实把他们几个数加起来就知道了,1、2、4、6 可以表达的范围是 0~13,而 1、2、4、8 可以表达的范围是 0~15,而我们要求的是表达 10,大于 10 的范围是不能被选择的。
所以我们可以在 1、2、4 (表达的范围是 0~7)的基础上,增加一个数 3(由 10 - 7 而来),这样就能满足我们需要表达的范围 0~10。
具体的转换为二进制的代码如下所示:
class Solution {public int maxValue(int N, int C, int[] s, int[] v, int[] w) {// 扁平化List<Integer> worth = new ArrayList<>();List<Integer> volume = new ArrayList<>();// 我们希望每件物品都进行扁平化,所以首先遍历所有的物品for (int i = 0; i < N; i++) {// 获取每件物品的出现次数int val = s[i];// 进行扁平化:如果一件物品规定的使用次数为 7 次,我们将其扁平化为三件物品:1*重量&1*价值、2*重量&2*价值、4*重量&4*价值// 三件物品都不选对应了我们使用该物品 0 次的情况、只选择第一件扁平物品对应使用该物品 1 次的情况、只选择第二件扁平物品对应使用该物品 2 次的情况,只选择第一件和第二件扁平物品对应了使用该物品 3 次的情况 ... //注意此处是等号,可能正好减完for (int k = 1; k <= val; k *= 2) { val -= k;worth.add(w[i] * k);volume.add(v[i] * k);}if (val > 0) {//没有正好减完worth.add(w[i] * val);volume.add(v[i] * val);}}// 0-1 背包问题解决方案int[] dp = new int[C + 1];for (int i = 0; i < worth.size(); i++) {for (int j = C; j >= volume.get(i); j--) {dp[j] = Math.max(dp[j], dp[j - volume.get(i)] + worth.get(i));}}return dp[C];}
}
相关文章:
多重背包问题中的二进制状态压缩
1.多重背包问题 经典的多重背包问题和01背包问题的相似之处在于二者的一维遍历顺序都是从右侧往左侧遍历。 同时多重背包的一维写法不比二维写法降低时间复杂度。 2.多重背包标准写法:(平铺展开形式) class Solution {public int maxValue(int N, int C, int[] s…...
汇编语言程序设计(四)之汇编指令
系列文章 汇编语言程序设计(一) 汇编语言程序设计(二)之寄存器 汇编语言程序设计(三)之汇编程序 汇编指令 1. 数据传输指令 指令包括:MOV、XCHG、XLAT、LEA、LDS、LES、PUSH、POP、PUSHF、LA…...
Vant2 源码分析之 vant-sticky
前言 原打算借鉴 vant-sticky 源码,实现业务需求的某个功能,第一眼看以为看懂了,拿来用的时候,才发现一知半解。看第二遍时,对不起,是我肤浅了。这里侧重分析实现原理,其他部分不拓展开来&…...
【自然语言处理】【大模型】大语言模型BLOOM推理工具测试
相关博客 【自然语言处理】【大模型】大语言模型BLOOM推理工具测试 【自然语言处理】【大模型】GLM-130B:一个开源双语预训练语言模型 【自然语言处理】【大模型】用于大型Transformer的8-bit矩阵乘法介绍 【自然语言处理】【大模型】BLOOM:一个176B参数…...
云桌面技术初识:VDI,IDV,VOI,RDS
VDI(Virtual Desktop Infrastucture,虚拟桌面架构),俗称虚拟云桌面 VDI构架采用的“集中存储、集中运算”构架,所有的桌面以虚拟机的方式运行在服务器硬件虚拟化层上,桌面以图像传输的方式发送到客户端。 …...
基于本地centos构建gdal2.4.4镜像
1.前言 基于基础镜像构建gdal环境一般特别大,一般少则1.6G,多则2G甚至更大,这对于镜像的迁移造成了极大的不便。究其原因在于容器中有大量的源码文件以及编译中间过程文件,还要大量编译需要的yum库。本文主要通过在centos系统上先…...
生产环境线程问题排查
线程状态的解读RUNNABLE线程处于运行状态,不一定消耗CPU。例如,线程从网络读取数据,大多数时间是挂起的,只有数据到达时才会重新唤起进入执行状态。只有Java代码显式调用sleep或wait方法时,虚拟机才可以精准获取到线程…...
Day908.joinsnljdist和group问题和备库自增主键问题 -MySQL实战
join&snlj&dist和group问题和备库自增主键问题 Hi,我是阿昌,今天学习记录的是关于join&snlj&dist和group问题和备库自增主键问题的内容。 一、join 的写法 join 语句怎么优化?中,在介绍 join 执行顺序的时候&am…...
算法 - 剑指Offer 丑数
题目 我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。 解题思路 这题我使用最简单方法去做, 首先我们可以获取所有2n,3n,5*n的丑数,只是我们这里暂时无法排序,并且可能…...
【ONE·C || 文件操作】
总言 C语言:文件操作。 文章目录总言1、文件是什么?为什么需要文件?1.1、为什么需要文件?1.2、文件是什么?2、文件的打开与关闭2.1、文件指针2.2、文件打开和关闭:fopen、fclose2.3、文件使用方式3、文…...
cmd窗口中java命令报错。错误:找不到或无法加载主类 java的jdk安装过程中踩过的坑
错误: 找不到或无法加载主类 HelloWorld 遇到这个问题时,我尝试过网上其他人的做法。有试过添加classpath,也有试过删除classpath。但是依然报错,这里javac可以编译通过,说明代码应该是没有问题的。只是在运行是出现了错误。我安装…...
Breathwork(呼吸练习)
查了下呼吸练习相关内容,做个记录。我又在油管学习啦。 喜欢在you. tube看一些self-help相关的内容。比如学习方法、拉伸、跑步、力量举、自重锻炼等等。 总是听Obi Vicent说起Breathwork,比如: My 6am Morning Routine | New Healthy Habit…...
taobao.itemprops.get( 获取标准商品类目属性 )
¥开放平台基础API不需用户授权 通过设置必要的参数,来获取商品后台标准类目属性,以及这些属性里面详细的属性值prop_values。 公共参数 请求地址: HTTP地址 http://gw.api.taobao.com/router/rest 公共请求参数: 公共响应参数: 请求参数 点…...
QT配置安卓环境(保姆级教程)
目录 下载环境资源 JDK1.8 NDK SDK 安装QT 配置环境 下载环境资源 JDK1.8 介绍JDK是Java开发的核心工具,为Java开发者提供了一套完整的开发环境,包括开发工具、类库和API等,使得开发者可以高效地编写、测试和运行Java应用程序。 下载…...
【uni-app教程】八、UniAPP Vuex 状态管理
八、UniAPP Vuex 状态管理 概念 Vuex 是一个专为 Vue.js 应用程序开发的状态管理模式。它采用集中式存储管理应用的所有组件的状态,并以相应的规则保证状态以一种可预测的方式发生变化。 应用场景 Vue多个组件之间需要共享数据或状态。 关键规则 State:…...
同花顺测试面经(30min)
大概三十分钟,面试官人还挺好的 1.自我介绍 2.详细问你了自我介绍中的一个实习经历 3.对我们公司有什么了解 !!(高频) 4.对测试有什么看法,为什么选测试 5.黑盒白盒分别是什么 6.对测试左移有什么看法…...
C++-简述#ifdef、#else、#endif和#ifndef的作用
回答如下: #ifdef,#else,#endif和#ifndef都是预处理指令,用于条件编译。#ifdef:这个指令用来判断一个宏是否已经被定义过,如果已经定义过,则执行后面的代码块。#else:这个指令一般与…...
VictoriaMetrics 集群部署
官网 ## 官网 https://github.com/VictoriaMetrics/VictoriaMetrics 集群角色详解 VictoriaMetrics 集群模式。主要由 vmstorage ,vminsert,vmselect 三部分组成,这三个组件每个组件都可以单独进行扩展。其中: vmstorage 负责提供数据存储服务vminsert 是数据存…...
【基于感知损失的无监督泛锐化】
PercepPan: Towards Unsupervised Pan-Sharpening Based on Perceptual Loss (PercepPan:基于感知损失的无监督泛锐化) 在基于神经网络的全色锐化文献中,作为地面实况标签的高分辨率多光谱图像通常是不可用的。为了解决这个问题…...
在vercel上用streamlit部署网站
Verce和Streamlit都是非常流行的Web应用程序部署平台。以下是从零开始在Vercel上部署Streamlit应用程序的一些基本步骤。 安装 Streamlit 在本地计算机上安装Streamlit。可以轻松地通过在命令行中运行以下命令来安装: pip install streamlit为 Streamlit 应用程序…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
