背包问题(动态规划)
背包问题是一种组合优化的问题,它有多种变体,但最常见的两种是0/1背包问题和完全背包问题。
0/1背包问题
问题描述: 假设你有一个背包,背包的容量为W(可以是重量或者体积等度量),同时有n个物品,每个物品都有自己的重量w[i]和价值v[i]。现在的目标是选择一些物品放入背包,使得背包中物品的总价值最大,但背包的总重量不能超过W。
特点:
-
每个物品只能选择一次,即不能分割。
-
选择放入背包或者不放入背包。
解决方案:
动态规划:这是解决0/1背包问题最常见的方法。通过构建一个二维数组dp,其中dp[i] [j]表示考虑前i个物品,背包容量为j时的最大价值。状态转移方程为: dp[i] [j]=max(dp[i−1] [j],dp[i−1] [j−w[i]]+v[i]), dp[i] [j]=max(dp[i−1] [j],dp[i−1] [j−w[i]]+v[i]) 其中,如果选择第i个物品,则背包容量减去该物品的重量,总价值加上该物品的价值;如果不选择,则总价值不变。
已知w[]和v[]
int[][] dp = new int[n + 1][m + 1]for(int i = 1; i <= n; i++) {//遍历物品,注意下标的对应关系,这里都假设物品从下标1开始记录for(int j = 1; j <= m; j++) {//遍历容量if(j >= w[i])dp[i][j] = Math.max(d[i-1][j], dp[i-1][j-w[i]] + v[i]); }
}
但是我们观察动态规划方程发现:对于考虑前i个物品的时候我们只需要用到i-1这一个状态,所以我们能不能将二维的数组压缩成一维的呢?答案显然是可以的
我们现在设dp[j]是容量j时的最大价值,因为我们外层循环的i一直在自增,所以对于上一次的dp[j]就相当与dp[i-1] [j], 所以我们只要不断更新dp[j]就行。那是否是在上述代码的基础上将递推方程由 dp[i] [j]=max(dp[i−1] [j],dp[i−1] [j−w[i]]+v[i])改为dp[j] = max(dp[j], dp[j-w[i]] + v[i])就万事大吉了呢?宝贝你显然是太天真了
我们再来捋一下,如果我们用for(int j = 1; j <= m; j++),我们每次更新都是从低位开始的,并且后续的递推要用到前面的结论,那我们来举例一下:
如果有3个物品他们的花费和价值是
W: 1 2 3
V: 2 1 3
对于容量为5的背包
i=1时
dp[1]=2, dp[2] = 4, dp[3] = 6, dp[4] = 8, dp[5] = 10 有没有发现端倪为毛我这次的修改全体现到之后的更新上了这不对吧,按我们的设想因该是i=2的那次才会应用上才对(但是这在完全背包问题中会被用到)
我们换倒序一下for(int j = m; j > 0; j--)
i=1时
dp[5] = 2, dp[4] = 2, dp[3] = 2, dp[2] = 2, dp[1] = 2;
i=2时
dp[5] = 3, dp[4] = 3, d[3] = 3, dp[2] = 2, dp[1] = 2
i=3时
dp[5] = 5, dp[4] = 5, d[3] = 3, dp[2] = 2, dp[1] = 2
这不就全对上了嘛,所以倒序可以避免这次的修改影响这次其它容量时的更新
代码如下:
已知w[]和v[]
int[] dp = new int[m + 1]for(int i = 1; i <= n; i++) {//遍历物品,注意下标的对应关系,这里都假设物品从下标1开始记录for(int j = m; j > 0; j--) {//遍历容量dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]); }
}
还有个无伤大雅的小优化,for(int j = m; j >= w[i]; j--), 因为你剩余的空间如果都放不下这个物体了,那这个物体的价值自然不会对答案产生影响,并且后续的遍历中也不存在能放得下这个物体的情况,可以直接跳过
已知w[]和v[]
int[] dp = new int[m + 1]for(int i = 1; i <= n; i++) {//遍历物品,注意下标的对应关系,这里都假设物品从下标1开始记录for(int j = m; j >= w[i]; j--) {//遍历容量dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]); }
}
完全背包问题
问题描述: 与0/1背包问题类似,但每个物品可以无限次选择。
特点:
-
每个物品可以被选择多次。
解决方案:
-
动态规划:同样使用动态规划,但是状态转移方程有所不同,因为物品可以被重复选择: dp[j]=max(dp[j],dp[j−w[i]]+v[i]) , dp[j]=max(dp[j],dp[j−w[i]]+v[i])其中,对于每个物品,我们尝试多次放入背包,直到背包容量不足以再放入该物品为止。
代码:
已知w[]和v[]
int[] dp = new int[m + 1]for(int i = 1; i <= n; i++) {//遍历物品,注意下标的对应关系,这里都假设物品从下标1开始记录for(int j = 1; j <= w; j++) {//遍历容量if(j >= w[i])dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]); }
}
相关文章:
背包问题(动态规划)
背包问题是一种组合优化的问题,它有多种变体,但最常见的两种是0/1背包问题和完全背包问题。 0/1背包问题 问题描述: 假设你有一个背包,背包的容量为W(可以是重量或者体积等度量),同时有n个物品…...
从0开始学习机器学习--Day26--聚类算法
无监督学习(Unsupervised learning and introduction) 监督学习问题的样本 无监督学习样本 如图,可以看到两者的区别在于无监督学习的样本是没有标签的,换言之就是无监督学习不会赋予主观上的判断,需要算法自己去探寻区别,第二张…...
Vue3插槽v-slot使用方式
在 Vue 3 中,v-slot 是用来定义和使用插槽的指令。插槽是 Vue 的一个功能,允许你在组件内部定义占位内容,便于在父组件中提供动态内容。以下是 v-slot 的详细使用方法: 1. 基础使用 <template><BaseComponent><te…...
Axure二级菜单下拉交互实例
1.使用boxlabe进行基础布局 2.设置鼠标悬浮和选中状态 3.转换为动态面板 选中所有二级菜单,进行按钮组转换 选中所有二级菜单,进行动态面板转换 4.给用户管理增加显示/隐藏事件 1)选择toggle代表上拉和下拉切换加载 2)勾选Bring to Front,并选择Push/Pull Widgets代表收缩时…...
华为VPN技术
1.启动设备 2.配置IP地址 [FW1]int g1/0/0 [FW1-GigabitEthernet1/0/0]ip add 192.168.1.254 24 [FW1-GigabitEthernet1/0/0]int g1/0/1 [FW1-GigabitEthernet1/0/1]ip add 100.1.1.1 24 [FW1-GigabitEthernet1/0/1]service-manage ping permit [FW2]int g1/0/0 [FW2-Gi…...
CommonsBeanutils与Shiro发序列化利用的学习
一、前言 前面的学习中,过了一遍cc1-cc7的利用链,在CC2的利用链中,学习了 java.util.PriorityQueue,它在Java中是一个优先队列,队列中每一个元素都有自己的优先级。在反序列化这个对象时,为了保证队列顺序…...
运维云计算SRE-第2周
1. 总结学过的权限,属性及ACL相关命令及选项,示例。 一、Linux安全模型 (一)资源分派 Authentication(认证):验证用户身份,确保登录系统的用户是合法的。 Authorization(…...
React Native 全栈开发实战班 - 用户界面进阶之响应式设计实践
在移动应用开发中,响应式设计 是确保应用在不同设备、屏幕尺寸和方向下都能提供良好用户体验的关键。React Native 提供了多种工具和技巧来实现响应式设计,包括 Flexbox 布局、动态样式、屏幕尺寸适配等。本章节将详细介绍如何在 React Native 中进行响应…...
SlickGrid点击/双击事件
分析 SlickGrid提供了点击事件方法grid.onClick和grid.onDblClick用于捕获用户对表格列的点击,捕获到点击事件之后,修改表格数据,然后使用grid.updateRow方法将修改后的数据更新到表格中。 展示 代码 创建grid(HTML)…...
一文详细深入总结服务器选型
1. 题记: 服务器选型工作是项目规划检讨的一项非常重要的工作,本文详细深入总结服务器选型。 2. 服务器基础知识概览 2.1 服务器的定义与功能 2.1 .1 定义 服务器是一种高性能计算机,其设计目的是在网络中提供服务。它可以处理来自多个客…...
一、Nginx反向代理(七层代理)二、Nginx的TCP/UDP调度器(四层代理)
一、Nginx反向代理(七层代理) 实验要求 使用Nginx实现Web反向代理功能,实现如下功能: 后端Web服务器两台,可以使用httpd实现Nginx采用轮询的方式调用后端Web服务器两台Web服务器的权重要求设置为不同的值最大失败次数为…...
CSS+JQuery 实现弹力球效果,碰到屏幕边框弹回
实现弹力球效果,碰到屏幕边框弹回,效果如下 代码如下: <img src"../image/ball.png" alt"" class"ball"> <style>.ball {position: fixed;top: 50vh;left: 50vw;width: 15vw;height: 15vw;border…...
shell编程规范和脚本变量
什么是shell 人和计算机内核之间的中介: 计算机的语言是二进制,把人类的语言翻译成计算机能够识别的语言,然后让内核来处理 内核完成之后要把结果反馈给用户,要把计算机的翻译成人类能够识别的语言 命令解释器,pyc…...
jspm美容院管理系统
摘要 首先,论文一开始便是清楚的论述了系统的研究内容。其次,剖析系统需求分析,弄明白“做什么”,分析包括业务分析和业务流程的分析以及用例分析,更进一步明确系统的需求。然后在明白了系统的需求基础上需要进一步地设计系统,主要包罗软件架构模式、整体功能模块、数据库设计…...
Prometheus结合K8s(二)使用
上一篇介绍了如何搭建 Prometheus结合K8s(一)搭建-CSDN博客,这章介绍使用 页面访问 kubectl get svc -n prom 看promeheus和granfana的端口访问页面 Prometheus 点击status—target,可以看到metrics的数据来源,即各…...
【虚幻引擎】UE5数字人开发实战教程
本套课程将会交大家如何去开发属于自己的数字人,包含大模型接入,流式输出,语音识别,语音合成,口型驱动,动画蓝图,语音唤醒等功能。 课程介绍视频如下: 【虚幻引擎】UE5 历时一个多月…...
深入分析:固定参考框架在RViz中的作用与对数据可视化的影响 ros ubuntu20.04
深入分析:固定参考框架在RViz中的作用与对数据可视化的影响 RViz (Robot Visualization) 是 ROS (Robot Operating System) 中一种重要的三维可视化工具,主要用于实时观察和分析传感器数据、机器人状态信息以及环境模型。RViz的核心功能之一是固定参考框…...
Android:时间选择器(最下面有效果图)
1.创建DateUtil类 /*** Created by wangshuai on 2024/11/19.*/ public class DateUtil {public final static String PATTERN_ALL"yyyy-MM-dd HH:mm:ss";public final static String PATTERN_DEFAULT"yyyy-MM-dd";/*** 获取当前时间* return yyyy-MM-dd*…...
第十六届蓝桥杯模拟赛(第一期)-c++/c
c/c蓝桥杯模拟赛题解,非常详细 质因数 1、填空题 【问题描述】 如果一个数 p 是个质数,同时又是整数 a 的约数,则 p 称为 a 的一个质因数。 请问 2024 有多少个质因数。 【答案提交】 这是一道结果填空的题,你只需要算出结果后提…...
如何挑选路由器?需要看哪些参数?
挑选路由器时,选择合适的型号和参数对于确保家庭或办公网络的速度、稳定性和覆盖范围至关重要。以下是挑选路由器时需要考虑的关键参数和因素: 1. 无线标准 (Wi-Fi标准) 无线标准是衡量路由器性能的核心指标。不同的无线标准提供不同的速率、范围和技术…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
【Linux】自动化构建-Make/Makefile
前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具:make/makfile 1.背景 在一个工程中源文件不计其数,其按类型、功能、模块分别放在若干个目录中,mak…...
0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化
是不是受够了安装了oracle database之后sqlplus的简陋,无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话,配置.bahs_profile后也能解决上下翻页这些,但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可,…...
ArcGIS Pro+ArcGIS给你的地图加上北回归线!
今天来看ArcGIS Pro和ArcGIS中如何给制作的中国地图或者其他大范围地图加上北回归线。 我们将在ArcGIS Pro和ArcGIS中一同介绍。 1 ArcGIS Pro中设置北回归线 1、在ArcGIS Pro中初步设置好经纬格网等,设置经线、纬线都以10间隔显示。 2、需要插入背会归线…...
RabbitMQ 各类交换机
为什么要用交换机? 交换机用来路由消息。如果直发队列,这个消息就被处理消失了,那别的队列也需要这个消息怎么办?那就要用到交换机 交换机类型 1,fanout:广播 特点 广播所有消息:将消息…...
JavaScript性能优化实战大纲
性能优化的核心目标 降低页面加载时间,减少内存占用,提高代码执行效率,确保流畅的用户体验。 代码层面的优化 减少全局变量使用,避免内存泄漏 // 不好的实践 var globalVar I am global;// 好的实践 (function() {var localV…...
