算法体系-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 范围讨论模型范围尝试模型 (这种模型特别在乎讨论开头如何如何 结尾如何如何) 玩家博弈问题,玩家玩纸牌只能那左或者右 0.3 …...
字符集相关变量理解
建表 创建一个新表,想让他的字符集是 gbk,怎么弄? 尝试1: 失败!原因: set names gbk; 等价于:set character_set_client gbk; set character_set_connection gbk; set character_set_results gbk;尝…...
618哪些数码产品比较好?2024超高人气产品推荐!
随着6.18大促的脚步渐近,你是否已经按捺不住内心的激动,想要在网络购物的海洋中畅游,尽情享受购物的狂欢?然而,面对繁多的商品和各式各样的优惠活动,你是否感到了一丝迷茫?作为一位经验丰富的网…...
基础-01-计算机网络概论
一. 计算机网络的发展与分类 1.计算机网络的形成与发展 计算机网络:计算机技术与通信技术的结合 ICTITCT 2.计算机网络标准阶段 3.计算机网络分类1:通信子网和资源子网 通信子网:通信节点(集线器、交换机、路由器等)和通信链路(电话线、同轴电缆、无线电线路、卫…...
STM32学习笔记(一)--时钟树详解
(1)时钟概述;时钟是具有周期性的脉冲信号,最常用的是占空比50%的方波。(时钟相当于单片机的脉搏;STM32本身非常复杂,外设非常的多,为了保持低功耗工作,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 是一个强大的前端框架,它为开发者提供了一系列的CSS工具和组件,以便快速构建响应式、移动优先的网站。本参考手册旨在为那些希望深入了解和使用Foundation CSS的开发者提供一个全面的指南。 基础知识 1…...
方法递归-结合案例阶乘问题、求和问题和猴子吃桃问题
方法递归 递归是一种算法 在程序设计语言中广泛应用. 从形式上来说:方法调用自身的形式称为方法递归(recursion). 递归的形式: 直接递归:方法调用自己。间接递归:方法调用其他方法,其他方法…...
有一个主域名跟多个二级子域名时该怎么申请SSL证书?
当您拥有主域名以及多个子域名时,选择合适的SSL证书类型对于确保网站的安全性至关重要。以下是三种SSL证书类型的简要介绍: 单域名SSL证书: 功能:只能绑定单个域名,无论是主域名还是子域名。 适用场景:仅…...
LabVIEW伺服电机可应用在哪些领域
LabVIEW与伺服电机的结合,得益于LabVIEW强大的图形编程能力和伺服电机的高精度、高响应速度,广泛应用于多个领域。以下是一些主要应用领域: 1. 工业自动化 数控机床控制 LabVIEW用于控制伺服电机在数控机床中的运动,实现高精度的…...
nvidia 显卡 没有正确安装或配置 OpenGL 库
看到这个错误可能意味着你的系统没有正确安装或配置 OpenGL 库。以下是一些步骤来解决这个问题: 1. 安装必要的软件包 确保你已经安装了必要的软件包,包括 mesa-utils 和 nvidia-driver。 安装 mesa-utils sudo apt update sudo apt install mesa-ut…...
将自己md文件发布到自己的博客园实现文件的持久化存储
上传markdown文件到博客园 目录 【0】需求原因【1】功能【2】环境【最佳实践测试】 (1)查看 Typora 设置(2)配置 pycnblog 配置文件 config.yaml(3)运行 pycnblog 中的文件 cnblog_markdown.cmd࿰…...
uni-app的生命周期(应用,页面生命周期)
1. uni-app的生命周期(应用,页面生命周期) 1.1. 应用生命周期 1.1.1. 定义在app.vue中 生命周期函数名说明onLaunch当uni-app 初始化完成时触发(全局只触发一次)onShow当 uni-app 启动,或从后台进入前台…...
响应式企业网站建站系统源码 模版丰富+一站式建站 全开源可二次开发 带源码包+搭建部署教程
系统概述 在数字化转型的浪潮中,企业官网作为品牌展示、产品推广及客户服务的重要窗口,其建设质量直接影响着企业的线上形象与市场竞争力。响应式企业网站建站系统源码的出现,为企业提供了一种高效、灵活且成本可控的建站解决方案。 代码示…...
如何解除内存卡的写保护并格式化为exFAT文件系统
最近有客户提问内存卡提示写保护,且无法格式化为exFAT格式的问题,可能是由于多种原因引起的。以下是一些可能的解决方法: 1. 检查物理写保护开关 一些SD卡和MicroSD卡适配器上有一个小的物理开关,可以启用或禁用写保护。确保这个…...
【 EI会议 | 西南大学主办 | 往届均已实现检索】第三届神经形态计算国际会议(ICNC 2024)
第三届神经形态计算国际会议(ICNC 2024) 2024 3rd International Conference on Neuromorphic Computing (ICNC 2024) 一、重要信息 大会官网:www.ic-nc.org(点击投稿/参会/了解会议详情) 会议时间:2024年12月13-15…...
利用python爬虫采集苹果公司各产品销售收入统计报告
数据为2013年到2022年苹果公司各产品(iPhone、iPad、Mac等)及服务的销售收入。iPhone是苹果公司销售收入最高的产品。 数据统计单位为:亿美元 。 数据说明: 数据整理自苹果公司历年10-K文件,每年10-K文件可能对之前年…...
ethercat igh可能出现的两个bug
1. 插入网线直接就进入op状态,这可能是因为 从站支持eoe协议 igh对eoe协议支持的从站默认使其直接进入op状态,可以修改igh源码编译选项,不启动eoe协议 可以参考: igh编译选项 igh一些EoE协议说明 Automatic Configuration&#…...
计算机网络知识点(三)
目录 一、简述TCP连接和关闭的状态转移 二、简述TCP慢启动 三、简述TCP如何保证有序 四、简述TCP常见的拥塞控制算法 五、简述TCP超时重传 一、简述TCP连接和关闭的状态转移 状态转移图 图中上半部分是TCP的三次握手过程的状态变迁,下半部分是TCP四次挥手过程的…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
土建施工员考试:建筑施工技术重点知识有哪些?
《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目,核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容,附学习方向和应试技巧: 一、施工组织与进度管理 核心目标: 规…...
Python第七周作业
Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt,并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径,并创建logs目录(若不存在) 3.递归遍历目录data,输出所有.csv文件的路径…...
