01背包问题
背包问题的递归解决过程如下:
第一步明确思路
在解决问题之前,为描述方便,首先定义一些变量:Vi表示第 i 个物品的价值,Wi表示第 i 个物品的体积,定义V(i,j):当前背包容量 j,前 i 个物品最佳组合对应的价值,同时背包问题抽象化(X1,X2,…,Xn,其中 Xi 取0或1,表示第 i 个物品选或不选)。
1、建立模型,即求max(V1X1+V2X2+…+VnXn);
2、寻找约束条件,W1X1+W2X2+…+WnXn<capacity;
3、寻找递推关系式,面对当前商品有两种可能性:
包的容量比该商品体积小,装不下,此时的价值与前i-1个的价值是一样的,即V(i,j)=V(i-1,j);
还有足够的容量可以装该商品,但装了也不一定达到当前最优价值,所以在装与不装之间选择最优的一个,即V(i,j)=max{V(i-1,j),V(i-1,j-w(i))+v(i)}。
其中V(i-1,j)表示不装,V(i-1,j-w(i))+v(i) 表示装了第i个商品,背包容量减少w(i),但价值增加了v(i);
由此可以得出递推关系式:
j<w(i) V(i,j)=V(i-1,j)
j>=w(i) V(i,j)=max{V(i-1,j),V(i-1,j-w(i))+v(i)}
第二步填表
第三步回溯找到所选商品
背包问题最优解回溯
通过上面的方法可以求出背包问题的最优解,但还不知道这个最优解由哪些商品组成,故要根据最优解回溯找出解的组成,根据填表的原理可以有如下的寻解方式:
V(i,j)=V(i-1,j)时,说明没有选择第i 个商品,则回到V(i-1,j);
V(i,j)=V(i-1,j-w(i))+v(i)时,说明装了第i个商品,该商品是最优解组成的一部分,随后我们得回到装该商品之前,即回到V(i-1,j-w(i));
一直遍历到i=0结束为止,所有解的组成都会找到
相关文章:
01背包问题
背包问题的递归解决过程如下: 第一步明确思路 在解决问题之前,为描述方便,首先定义一些变量:Vi表示第 i 个物品的价值,Wi表示第 i 个物品的体积,定义V(i,j):当前背包容量 j,前 i 个…...
14_FreeRTOS二值信号量
目录 信号量的简介 队列与信号量的对比 二值信号量 二值信号量相关API函数 实验源码 信号量的简介 信号量是一种解决同步问题的机制,可以实现对共享资源的有序访问。 假设有一个人需要在停车场停车 1.首先判断停车场是否还有空车位(判断信号量是否有资源) 2.停车场正好…...
JavaScript随手笔记---轮播图(点击切换)
💌 所属专栏:【JavaScript随手笔记】 😀 作 者:我是夜阑的狗🐶 🚀 个人简介:一个正在努力学技术的CV工程师,专注基础和实战分享 ,欢迎咨询! &#…...
机器人学 markdown数学公式常用语法
参考链接1 本文包含了markdown常用的数学公式,按照目录可查询选用 初始类 行内数学公式均用两个符号包裹行间数学公式均用两个符号包裹 行间数学公式均用两个符号包裹行间数学公式均用两个符号包裹,用于表示重要的、需在行间单独列出的公式 $行内数学…...
如何使用 Python 语言来编码和解码 JSON 对象
JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式,易于人阅读和编写。 JSON 函数 使用 JSON 函数需要导入 json 库:import json。 函数 描述 json.dumps 将 Python 对象编码成 JSON 字符串 json.loads 将已编码的 JSON 字符串解码为 Pyth…...
【蓝桥云课】求正整数的约数个数
一、求正整数n的约数个数 方法一(常用算法):从1到n逐一判断其能否整除n,若能整除n即为n的约数,否则不是n的约数。 方法二:从1到n\sqrt{n}n逐一判断是否为n的约数,当n\sqrt{n}n为n的约数时,个数加1&…...
刷题记录: wannafly25 E 牛客NC19469 01串 [线段树维护动态dp]
传送门:牛客 题目描述: Bieber拥有一个长度为n的01 串,他每次会选出这个串的一个子串作为曲谱唱歌,考虑该子串从左 往右读所组成的二进制数P。 Bieber每一秒歌唱可以让P增加或减少 2 的 k次方(k由Bieber选 定),但必须…...
懂九转大肠的微软New Bing 内测申请教程
最近微软的New Bing开放内测了,网上已经有拿到内测资格的大佬们对比了ChatGPT和New Bing。对比结果是New Bing比ChatGPT更强大。来看看具体对比例子吧 1.时效性更强 ChatGPT的库比较老,跟不上时事,比如你问它九转大肠的梗,ChatG…...
WRAN翻译
基于小波的图像超分辨残差注意力网络 Wavelet-based residual attention network for image super-resolution 代码: https://github.com/xueshengke/WRANSR-keras 摘要: 图像超分辨率技术是图像处理和计算机视觉领域的一项基础技术。近年来,…...
ROS学习笔记——第二章 ROS通信机制
主要跟着[1]学习ros::Rate r(1); //错误,应改为ros::Rate r(10);[2]对Topic通信打的比方很形象,便于理解记忆。[3]有整个过程的图片,对于初学者更加友好[4]对发布者的代码注释非常好,方便进一步学习此外CMake官方文档可以查询相关…...
MacOS Pytorch 机器学习环境搭建
学习 Pytorch ,首先要搭建好环境,这里将采用 Anoconda Pytorch PyCharm 来一起构建 Pytorch 学习环境。 1. Anoconda 安装与环境创建 Anoconda 官方介绍:提供了在一台机器上执行 Python/R 数据科学和机器学习的最简单方法。 为什么最简单…...
项目——博客系统
文章目录项目优点项目创建创建相应的目录,文件,表,导入前端资源实现common工具类实现拦截器验证用户登录实现统一数据返回格式实现加盐加密类实现encrypt方法实现decrypt方法实现SessionUtil类实现注册页面实现前端代码实现后端代码实现登录页…...
PHP(14)会话技术
PHP(14)会话技术一、概念二、分类三、cookie技术1. cookie的基本使用2. cookie的生命周期3. cookie的作用范围4. cookie的跨子域5. cookie的数组数据四、session1. session原理2. session基本使用3. session配置4. 销毁session一、概念 HTTP协议是一种无…...
对JAVA 中“指针“理解
对于Java中的指针,以下典型案例会让你对指针的理解更加深刻。 首先对于: 系统自动分配对应空间储存数字 1,这个空间被变量名称b所指向即: b ——> 1 变量名称 空间 明…...
功率放大器在MEMS微结构模态测试研究中的应用
实验名称:功率放大器在MEMS微结构模态测试研究中的应用研究方向:元器件测试测试目的:随着MEMS器件在各个领域中广泛应用,对微结构进行模态测试获得其动态特性参数对微结构的设计、仿真、制造、以及质量控制和评价等方面具有十分重…...
【算法基础】字典树(Trie树)
一、Trie树原理介绍 1. 基本概念 Trie 树,也叫“字典树”。顾名思义,它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。【高效存储和查找字符串集合的数据结构】,存储形式如下: 2. 用数组来模拟Trie树的…...
MyBatis 插件 + 注解轻松实现数据脱敏
问题在项目中需要对用户敏感数据进行脱敏处理,例如身份号、手机号等信息进行加密再入库。解决思路就是:一种最简单直接的方式,在所有涉及数据敏感的查询到对插入时进行密码加解密方法二:有方法一到出现对所有重大问题的影响&#…...
MySQL优化篇-MySQL压力测试
备注:测试数据库版本为MySQL 8.0 MySQL压力测试概述 为什么压力测试很重要?因为压力测试是唯一方便有效的、可以学习系统在给定的工作负载下会发生什么的方法。压力测试可以观察系统在不同压力下的行为,评估系统的容量,掌握哪些是重要的变化…...
CF43A Football 题解
CF43A Football 题解题目链接字面描述题面翻译题面描述题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1样例 #2样例输入 #2样例输出 #2代码实现题目 链接 https://www.luogu.com.cn/problem/CF43A 字面描述 题面翻译 题面描述 两只足球队比赛,现给你进…...
Nginx常用命令及具体应用(Linux系统)
目录 一、常用命令 1、查看Nginx版本命令,在sbin目录下 2、检查配置文件的正确性 3、启动和停止Nginx 4、查看日志,在logs目录下输入指令: 5、重新加载配置文件 二、Nginx配置文件结构 三、Nginx具体应用 1、部署静态资源 2、反向代…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
莫兰迪高级灰总结计划简约商务通用PPT模版
莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用
在工业制造领域,无损检测(NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统,以非接触式光学麦克风技术为核心,打破传统检测瓶颈,为半导体、航空航天、汽车制造等行业提供了高灵敏…...
在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...
认识CMake并使用CMake构建自己的第一个项目
1.CMake的作用和优势 跨平台支持:CMake支持多种操作系统和编译器,使用同一份构建配置可以在不同的环境中使用 简化配置:通过CMakeLists.txt文件,用户可以定义项目结构、依赖项、编译选项等,无需手动编写复杂的构建脚本…...
