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、反向代…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
Vite中定义@软链接
在webpack中可以直接通过符号表示src路径,但是vite中默认不可以。 如何实现: vite中提供了resolve.alias:通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...
