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

算法体系-20 第二十节暴力递归到动态规划

前言 动态规划模型从尝试暴力递归到傻缓存到动态规划

四种模型和体系班两种模型一共六种模型

0.1 从左往右模型

0.2 范围讨论模型范围尝试模型 (这种模型特别在乎讨论开头如何如何 结尾如何如何)

玩家博弈问题,玩家玩纸牌只能那左或者右

0.3 样本对应样本对应模型(特别在乎两个样本结尾如何如何 最长公共子序列)

0.4 业务限制模型

动态规划只是暴力尝试的一个缓存
 

1.2 分析

到当前货物的时候有两种选择,要么选择当前货物,要么不选择当前货物

base 条件的判断分析

if (rest < 0) {

return -1;}

这里为什么不能取return 0,因为上由传下来的剩下的bags的重量要大于0上由的值才是有意义的;

递归改动态规划

第一步找确定的值

if (index == w.length) {

return 0;

}

第二步找动态的值喝确定值之间的关系,动态的值时如何根据静态值退出来的

int p1 = process(w, v, index + 1, rest);

int next = process(w, v, index + 1, rest - w[index]);

这辆动态函数都需要依赖他的一行,最后一行又是确定值

1.3 尝试递归代码

// 所有的货,重量和价值,都在w和v数组里// 为了方便,其中没有负数// bag背包容量,不能超过这个载重// 返回:不超重的情况下,能够得到的最大价值public static int maxValue(int[] w, int[] v, int bag) {if (w == null || v == null || w.length != v.length || w.length == 0) {return 0;}// 尝试函数!return process(w, v, 0, bag);}// index 0~N// rest 负~bagpublic static int process(int[] w, int[] v, int index, int rest) {if (rest < 0) {return -1;}if (index == w.length) {return 0;}//不选择当前的货物int p1 = process(w, v, index + 1, rest);int p2 = 0;//要选择当前的货物int next = process(w, v, index + 1, rest - w[index]);if (next != -1) {p2 = v[index] + next;}return Math.max(p1, p2);}

1.4 改动态规划

递归改动态规划

第一步找确定的值

第二步找动态的值喝确定值之间的关系,动态的值时如何根据静态值退出来的

改动态规划 看是否有重复的情况

下面的p(3,10)都会重复

1.5 动态规划代码

public static int dp(int[] w, int[] v, int bag) {if (w == null || v == null || w.length != v.length || w.length == 0) {return 0;}int N = w.length;int[][] dp = new int[N + 1][bag + 1];for (int index = N - 1; index >= 0; index--) {for (int rest = 0; rest <= bag; rest++) {int p1 = dp[index + 1][rest];int p2 = 0;int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];if (next != -1) {p2 = v[index] + next;}dp[index][rest] = Math.max(p1, p2);}}return dp[0][bag];}public static void main(String[] args) {int[] weights = { 3, 2, 4, 7, 3, 1, 7 };int[] values = { 5, 6, 3, 19, 12, 4, 2 };int bag = 15;System.out.println(maxValue(weights, values, bag));System.out.println(dp(weights, values, bag));}}

相关文章:

算法体系-20 第二十节暴力递归到动态规划

前言 动态规划模型从尝试暴力递归到傻缓存到动态规划 四种模型和体系班两种模型一共六种模型 0.1 从左往右模型 0.2 范围讨论模型范围尝试模型 &#xff08;这种模型特别在乎讨论开头如何如何 结尾如何如何&#xff09; 玩家博弈问题&#xff0c;玩家玩纸牌只能那左或者右 0.3 …...

字符集相关变量理解

建表 创建一个新表&#xff0c;想让他的字符集是 gbk&#xff0c;怎么弄? 尝试1&#xff1a; 失败&#xff01;原因&#xff1a; set names gbk; 等价于&#xff1a;set character_set_client gbk; set character_set_connection gbk; set character_set_results gbk;尝…...

618哪些数码产品比较好?2024超高人气产品推荐!

随着6.18大促的脚步渐近&#xff0c;你是否已经按捺不住内心的激动&#xff0c;想要在网络购物的海洋中畅游&#xff0c;尽情享受购物的狂欢&#xff1f;然而&#xff0c;面对繁多的商品和各式各样的优惠活动&#xff0c;你是否感到了一丝迷茫&#xff1f;作为一位经验丰富的网…...

基础-01-计算机网络概论

一. 计算机网络的发展与分类 1.计算机网络的形成与发展 计算机网络&#xff1a;计算机技术与通信技术的结合 ICTITCT 2.计算机网络标准阶段 3.计算机网络分类1:通信子网和资源子网 通信子网:通信节点(集线器、交换机、路由器等)和通信链路(电话线、同轴电缆、无线电线路、卫…...

STM32学习笔记(一)--时钟树详解

&#xff08;1&#xff09;时钟概述&#xff1b;时钟是具有周期性的脉冲信号&#xff0c;最常用的是占空比50%的方波。&#xff08;时钟相当于单片机的脉搏&#xff1b;STM32本身非常复杂&#xff0c;外设非常的多&#xff0c;为了保持低功耗工作&#xff0c;STM32 的主控默认不…...

JAVA小知识16:JAVA常用的API

一、Math 方法名说明public static int abs(int a)获取参数绝对值public static double ceil(double a)向上取整public static double floor(double a)向下取整public static int round(float a)四舍五入public static int max(int a,int b)获取两个int值中的较大值public s…...

PaddleDetection快速体验quick_start

1 快速体验 # 设置显卡 export CUDA_VISIBLE_DEVICES0# 用PP-YOLO算法在COCO数据集上预训练模型预测一张图片 python tools/infer.py -c configs/ppyolo/ppyolo_r50vd_dcn_1x_coco.yml -o use_gputrue weightshttps://paddledet.bj.bcebos.com/models/ppyolo_r50vd_dcn_1x_coc…...

《Foundation CSS 参考手册》

《Foundation CSS 参考手册》 引言 Foundation 是一个强大的前端框架&#xff0c;它为开发者提供了一系列的CSS工具和组件&#xff0c;以便快速构建响应式、移动优先的网站。本参考手册旨在为那些希望深入了解和使用Foundation CSS的开发者提供一个全面的指南。 基础知识 1…...

方法递归-结合案例阶乘问题、求和问题和猴子吃桃问题

方法递归 递归是一种算法 在程序设计语言中广泛应用. 从形式上来说&#xff1a;方法调用自身的形式称为方法递归&#xff08;recursion&#xff09;. 递归的形式&#xff1a; 直接递归&#xff1a;方法调用自己。间接递归&#xff1a;方法调用其他方法&#xff0c;其他方法…...

有一个主域名跟多个二级子域名时该怎么申请SSL证书?

当您拥有主域名以及多个子域名时&#xff0c;选择合适的SSL证书类型对于确保网站的安全性至关重要。以下是三种SSL证书类型的简要介绍&#xff1a; 单域名SSL证书&#xff1a; 功能&#xff1a;只能绑定单个域名&#xff0c;无论是主域名还是子域名。 适用场景&#xff1a;仅…...

LabVIEW伺服电机可应用在哪些领域

LabVIEW与伺服电机的结合&#xff0c;得益于LabVIEW强大的图形编程能力和伺服电机的高精度、高响应速度&#xff0c;广泛应用于多个领域。以下是一些主要应用领域&#xff1a; 1. 工业自动化 数控机床控制 LabVIEW用于控制伺服电机在数控机床中的运动&#xff0c;实现高精度的…...

nvidia 显卡 没有正确安装或配置 OpenGL 库

看到这个错误可能意味着你的系统没有正确安装或配置 OpenGL 库。以下是一些步骤来解决这个问题&#xff1a; 1. 安装必要的软件包 确保你已经安装了必要的软件包&#xff0c;包括 mesa-utils 和 nvidia-driver。 安装 mesa-utils sudo apt update sudo apt install mesa-ut…...

将自己md文件发布到自己的博客园实现文件的持久化存储

上传markdown文件到博客园 目录 【0】需求原因【1】功能【2】环境【最佳实践测试】 &#xff08;1&#xff09;查看 Typora 设置&#xff08;2&#xff09;配置 pycnblog 配置文件 config.yaml&#xff08;3&#xff09;运行 pycnblog 中的文件 cnblog_markdown.cmd&#xff0…...

uni-app的生命周期(应用,页面生命周期)

1. uni-app的生命周期&#xff08;应用&#xff0c;页面生命周期&#xff09; 1.1. 应用生命周期 1.1.1. 定义在app.vue中 生命周期函数名说明onLaunch当uni-app 初始化完成时触发&#xff08;全局只触发一次&#xff09;onShow当 uni-app 启动&#xff0c;或从后台进入前台…...

响应式企业网站建站系统源码 模版丰富+一站式建站 全开源可二次开发 带源码包+搭建部署教程

系统概述 在数字化转型的浪潮中&#xff0c;企业官网作为品牌展示、产品推广及客户服务的重要窗口&#xff0c;其建设质量直接影响着企业的线上形象与市场竞争力。响应式企业网站建站系统源码的出现&#xff0c;为企业提供了一种高效、灵活且成本可控的建站解决方案。 代码示…...

如何解除内存卡的写保护并格式化为exFAT文件系统

最近有客户提问内存卡提示写保护&#xff0c;且无法格式化为exFAT格式的问题&#xff0c;可能是由于多种原因引起的。以下是一些可能的解决方法&#xff1a; 1. 检查物理写保护开关 一些SD卡和MicroSD卡适配器上有一个小的物理开关&#xff0c;可以启用或禁用写保护。确保这个…...

【 EI会议 | 西南大学主办 | 往届均已实现检索】第三届神经形态计算国际会议(ICNC 2024)

第三届神经形态计算国际会议&#xff08;ICNC 2024) 2024 3rd International Conference on Neuromorphic Computing (ICNC 2024) 一、重要信息 大会官网&#xff1a;www.ic-nc.org&#xff08;点击投稿/参会/了解会议详情&#xff09; 会议时间&#xff1a;2024年12月13-15…...

利用python爬虫采集苹果公司各产品销售收入统计报告

数据为2013年到2022年苹果公司各产品&#xff08;iPhone、iPad、Mac等&#xff09;及服务的销售收入。iPhone是苹果公司销售收入最高的产品。 数据统计单位为&#xff1a;亿美元 。 数据说明&#xff1a; 数据整理自苹果公司历年10-K文件&#xff0c;每年10-K文件可能对之前年…...

ethercat igh可能出现的两个bug

1. 插入网线直接就进入op状态&#xff0c;这可能是因为 从站支持eoe协议 igh对eoe协议支持的从站默认使其直接进入op状态&#xff0c;可以修改igh源码编译选项&#xff0c;不启动eoe协议 可以参考&#xff1a; igh编译选项 igh一些EoE协议说明 Automatic Configuration&#…...

计算机网络知识点(三)

目录 一、简述TCP连接和关闭的状态转移 二、简述TCP慢启动 三、简述TCP如何保证有序 四、简述TCP常见的拥塞控制算法 五、简述TCP超时重传 一、简述TCP连接和关闭的状态转移 状态转移图 图中上半部分是TCP的三次握手过程的状态变迁&#xff0c;下半部分是TCP四次挥手过程的…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...