动态规划(Dynamic Programming)—— Java解释

一、基本思想

动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,并将子问题的求解结果存储起来避免重复求解,从而一步步获取最优解的处理算法。

动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解 )

动态规划的特性主要包括:

  1. 分解原问题:动态规划将原问题分解为若干个相似的子问题,这些子问题之间相互独立,并且每个子问题只需要解决一次。
  2. 储存子问题的解:动态规划会储存子问题的解,以避免重复计算,这是动态规划能够高效解决复杂问题的关键。
  3. 状态转移方程:动态规划的本质在于对问题状态的定义和状态转移方程的定义(状态以及状态之间的递推关系)。
  4. 无后效性:每个状态都是“过去历史的一个完整总结”,也就是说,每个状态都包含了它过去的历史信息,而不会受到未来状态的影响。
  5. 阶段性和相互联系性:动态规划通常将问题划分为若干个阶段,每个阶段都对应着一组状态,这些状态之间相互联系,构成了整个问题的状态转移过程。
  6. 决策变量和允许决策集合:在动态规划中,每个阶段都包含若干个决策变量,这些决策变量的取值范围称为允许决策集合。
  7. 状态变量和状态集合:描述各阶段状态的变量称为状态变量,常用sk表示第k阶段的状态变量,状态变量sk的取值集合称为状态集合,用Sk表示。

二、案例说明——背包问题

动态规划可以通过填表的方式来逐步推进,得到最优解。在填表法中,会为每个子问题预先计算出最优解并填入表中,然后通过查表来获取原问题的最优解。

背包问题:有一个背包,容量为4磅 , 现有如下物品

物品重量价格
吉他(G)11500
音响(S)43000
电脑(L)32000
  1. 要求达到的目标为装入的背包的总价值最大,并且重量不超出
  2. 要求装入的物品不能重复

背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品,如何选择物品放入背包使物品的价值最大。其中又分01背包和完全背包(完全背包指的是:每种物品都有无限件可用)

这里的问题属于01背包,即每个物品最多放一个。而无限背包可以转化为01背包。

思路: 利用动态规划来解决。

假设背包容量为weight,有 n 个物品,每个物品的重量为 w[i],价值为 v[i]

  1. dp[i][j] 表示前 `i` 个 物品,容量为j时的最大价值。 —— 定义动态规划的状态,通常是数组或集合
  2. dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]),表示在第i个物品和不放第i个物品中选取一个最优解。 —— 定义状态转移方程,根据问题最优解的定义,确定状态之间的转移关系
  3. dp[0][j] = 0,表示不选择任何物品时的价值为0。—— 确定最基本的子问题的解作为边界条件
  4. 填表,从第一个物品开始填表直到最后一个物品。—— 每个子问题的最优解填入对应的状态位置
  5. 查询最优解,dp[n][weight] 即前n个物品,容量为w时的最大价值。 —— 根据需求解的问题的目标状态去查询对应子问题的最优解
public staic int knapsack(int[] w, int[] v, int weight) {int n = w.length;int[][] dp = new int[n + 1][weigth + 1];for (int i = 0; i <= n; i++) {for (int j = 0; j <= weigth; j++) {if (i == 0 || j == 0) {dp[i][j] = 0;} else if (j < w[i - 1]) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);}}}return dp[n][weight];
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/182032.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

计算机毕设 基于大数据的社交平台数据爬虫舆情分析可视化系统

文章目录 0 前言1 课题背景2 实现效果**实现功能****可视化统计****web模块界面展示**3 LDA模型 4 情感分析方法**预处理**特征提取特征选择分类器选择实验 5 部分核心代码6 最后 0 前言 &#x1f525; 这两年开始毕业设计和毕业答辩的要求和难度不断提升&#xff0c;传统的毕…

在 Python 中使用 Selenium 按文本查找元素

我们将通过示例介绍在Python中使用selenium通过文本查找元素的方法。 在 Python 中使用 Selenium 按文本查找元素 软件测试是检查应用程序是否满足用户需求的技术。 该技术有助于使应用程序成为无错误的应用程序。 软件测试可以手动完成&#xff0c;也可以通过某些软件完成。…

AI:60-基于深度学习的瓜果蔬菜分类识别

🚀 本文选自专栏:AI领域专栏 从基础到实践,深入了解算法、案例和最新趋势。无论你是初学者还是经验丰富的数据科学家,通过案例和项目实践,掌握核心概念和实用技能。每篇案例都包含代码实例,详细讲解供大家学习。 📌📌📌在这个漫长的过程,中途遇到了不少问题,但是…

Unity地面交互效果——3、曲面细分基础知识

大家好&#xff0c;我是阿赵。   之前介绍了使用动态法线贴图混合的方式模拟轨迹的凹凸感&#xff0c;这次来讲一下更真实的凹凸感制作。不过在说这个内容之前&#xff0c;这一篇先要介绍一下曲面细分着色器(Tessellation Shader)的用法。 一、为什么要做曲面细分 之前通过法…

docker离线部署

docker离线部署 1、目的 在可以连接互联网的情况下&#xff0c;可以在线安装Docker《Linux下Docker安装部署》&#xff0c;如果遇到内网服务器就没有办法进行在线安装&#xff0c;那么需要使用离线安装的方法。 2、下载安装包 创建工作文件夹&#xff1a; mkdir /opt/dock…

window10 定时任务

window10 定时任务 1、背景2、目标3、思路4、实操4.1、设置定时任务4.2、配置策略4.3、验证 1、背景 项目上由于业务调试需要&#xff0c;开具了一台window10系统&#xff0c;此台window10为项目组公共使用&#xff0c;为防止误操作分配了不通的账号&#xff0c;日常使用各自账…

Redis-使用java代码操作Redis->java连接上redis,java操作redis的常见类型数据存储,redis中的项目应用

java连接上redisjava操作redis的常见类型数据存储redis中的项目应用 1.java连接上redis package com.zlj.ssm.redis;import redis.clients.jedis.Jedis;/*** author zlj* create 2023-11-03 19:27*/ public class Demo1 {public static void main(String[] args) { // …

「Verilog学习笔记」移位运算与乘法

专栏前言 本专栏的内容主要是记录本人学习Verilog过程中的一些知识点&#xff0c;刷题网站用的是牛客网 分析 1、在硬件中进行乘除法运算是比较消耗资源的一种方法&#xff0c;想要在不影响延迟并尽量减少资源消耗&#xff0c;必须从硬件的特点上进行设计。根据寄存器的原理&a…

宏转录组分析揭示不同土壤生境中氮循环基因的表达

发表期刊&#xff1a;msystems 发表时间&#xff1a;2023 影响因子&#xff1a;6.4 DOI: 10.1128/msystems.00315-23 01、研究背景 与空白土壤相比&#xff0c;植物根系和根际细菌之间的相互作用调节了氮&#xff08;N&#xff09;的循环过程&#xff0c;并创造了富含低分…

最近非常火的电子木鱼流量主小程序源码系统 带完整搭建教程

在当今数字化时代&#xff0c;人们对于休闲娱乐的需求越来越高。近年来&#xff0c;一种结合了传统文化和现代科技的新型休闲娱乐方式——电子木鱼&#xff0c;迅速在年轻人群中流行开来。电子木鱼流量主小程序源码系统的出现&#xff0c;为这种新型娱乐方式提供了更加便捷的途…

吴恩达《机器学习》4-1->4-5:多变量线性回归

一、引入多维特征 在多维特征中&#xff0c;我们考虑的不再是单一的特征&#xff0c;而是一组特征&#xff0c;例如房价模型中可能包括房间数、楼层等多个特征。这些特征将组成一个向量&#xff0c;表示为(&#x1d465;₁, &#x1d465;₂, . . . , &#x1d465;ₙ)&#x…

记一次pdjs时安装glob出现,npm ERR! code ETARGET和npm ERR! code ELIFECYCLE

如往常一样&#xff0c;我使用pdjs来编译proto文件&#xff0c;但出现了以下报错&#xff1a; 大致就是pdjs的util在尝试执行npm install glob^7.2.1 escodegen^1.13.0时出错了 尝试手动执行安装&#xff0c;escodegen被正确安装&#xff0c;但glob^7.2.1出错 npm ERR! code E…

陕西某小型水库雨水情测报及大坝安全监测项目案例

项目背景 根据《陕西省小型病险水库除险加固项目管理办法》、《陕西省小型水库雨水情测报和大坝安全监测设施建设与运行管理办法》的要求&#xff0c;为保障水库安全运行&#xff0c;对全省小型病险水库除险加固&#xff0c;建设完善雨水情测报、监测预警、防汛道路、通讯设备、…

安装anaconda时控制台conda-version报错

今天根据站内的一篇博客教程博客在此安装anaconda时&#xff0c;检查conda版本时报错如下&#xff1a; >>>>>>>>>>>> ERROR REPORT <<<<<<<<<<<< Traceback (most recent call last): File “D:\An…

办公套件全家桶 Office2019 mac中文版新功能

office 2019 mac是 Microsoft office 应用程序套件的最新版本。它包括流行的软件&#xff0c;例如 Microsoft Word、Excel、PowerPoint 和 Outlook&#xff0c;office 2019 比其前身有许多新功能和改进&#xff0c;包括增强的协作工具、与 OneDrive 和 SharePoint 等云服务的更…

MTK 拨打紧急电话接通时间过长问题分析

1、问题分析 从Log视频来看&#xff0c;通话接通时间过长&#xff0c;但是Modem Log来看&#xff0c;进行多两次拨号。 查看AP代码确实进行了两次拨号 AP界面查看确实只有一路通话 查看MTK原始代码&#xff0c;发现当紧急拨号失败后&#xff0c;上层换卡重试&#xff0c;界面不…

ActiveMq学习⑨__基于zookeeper和LevelDB搭建ActiveMQ集群

引入消息中间件后如何保证其高可用&#xff1f; 基于zookeeper和LevelDB搭建ActiveMQ集群。集群仅提供主备方式的高可用集群功能&#xff0c;避免单点故障。 http://activemq.apache.org/masterslave LevelDB&#xff0c;5.6版本之后推出了LecelDB的持久化引擎&#xff0c;它使…

【Windows-软件-FFmpeg】(01)通过CMD运行FFmpeg进行操作,快速上手

前言 通过"cmd"运行"ffmpeg"进行操作&#xff0c;快速上手&#xff1b; 实操 【实操一】 说明 使用"ffmpeg"来合并音频文件和视频文件 &#xff1b; 环境 Windows 11 专业版&#xff08;22621.2428&#xff09;&#xff1b; 代码 &#xf…

【入门Flink】- 04Flink部署模式和运行模式【偏概念】

部署模式 在一些应用场景中&#xff0c;对于集群资源分配和占用的方式&#xff0c;可能会有特定的需求。Flink为各种场景提供了不同的部署模式&#xff0c;主要有以下三种&#xff1a;会话模式&#xff08;Session Mode&#xff09;、单作业模式&#xff08;Per-Job Mode&…

ArcGIS for Android 禁止地图旋转

ArcGIS for Android 禁止地图旋转 话不多说&#xff0c;直接上代码&#xff01;&#xff01;&#xff01; public class LoadMap extends AppCompatActivity {// 地图private MapView mapView;private ArcGISMap map;Overrideprotected void onCreate(Bundle savedInstanceSta…