动态规划——切割钢条问题

一、动态规划

       动态规划算法通常用于解决最优化问题寻求最优解)。其思想与分治法类似,将待求解的问题分成若干个子问题,先求出子问题,再根据子问题的解求出原来问题中的解,与分支法不同的是,在动态规划中,这些子问题的解是不相互独立的

        采用动态规划求解的问题通常有以下性质:

        1.最优化原理:问题的最优解中包含的子问题的解也是最优的

        2.无后效性:即某阶段状态一旦确定,就不受该状态以后决策的影响,只与当前状态有关。

        3.有重叠子问题:子问题之间是不相互独立的,一个子问题在下一阶段的决策中可能被多次用到。(通常减少不必要的重复操作)

二、钢条切割问题        

        给定一段长度为 n 的钢条和一个价格表 pi ,求钢条切割方案使得销售收益 rn 最大。

长度I

1

2

3

4

5

6

7

8

9

10

价格pi

1

5

8

9

10

17

17

20

24

30

        案例:长度为 4 的钢条,如何切割使得销售额最高?

        考虑两种情况:1.切割成4个长度为1的钢条,总收益是4;

                                  2.切割成2个长度为2的钢条,总收益是10。

                                  3.切割成1个长度为1和一个长度为3的钢条,总收益是9

                                 4.切割成1个长度为4的钢条,总收益为9

        法一(易理解)

        对于求收益r[n]最大的切割方案(最优解)

        1.不切割,收益为 pn

        2.先将该钢条分为切为两根,则当该两根钢条的收益之和最大时(取最优解时),对应长度为n的钢条收益也最大,最优解的和就是当前情况的最优解,可以得出:

                r_{n}=max(p_{n},r_{n-1} +r_{1},r_{n-2} +r_{2},\cdots ,r_{1} +r_{n-1}) 

        法二 (简单)

        对于该求解方法可以改为一种相似但更简单的递归求解方法:

        将钢条从左边切割下长度为 i 的一段,只对右边剩下的长度为 n-i 的一段继续进行切割(递归求解),对左边的一段不再进行切割。

关于此想法的理解:

将长度为n的钢条分解为左边开始一段,以及剩余部分继续分解的结果(通过递归) 

或者理解为:对于一根长度为n钢条,总存在某种切割,会使得切出长度为 i 的钢条  (1\leq i\leq n)

           此时公式为:

                                r_{n}=\underset{1\leq i\leq n}{max}(p_{i}+r_{n-i})

           递归函数的伪代码为:

int get_best(int n)
{
	if(n<=0) return 0;
	int maxn=-1;
	for(int i=1;i<=n;i++)
		maxn=max(p[i]+get_best(n-i),maxn);  // 通过递归求出最大
	//r[n]=maxn;
	return maxn;
}

        根据代码不难发现,在递归函数get_best中,会存在同一个变量反复递归的情况,从而引起时间的浪费,此时时间复杂度达到 O(2^n)

        需要通过剪枝的方法避免重复的操作(自顶向下法)

int get_best(int n)
{
	if(n<=0) return 0;
	if(r[n]>0) return r[n]; // 若已经访问过,即找到r[n]的最优解时,直接返回
	int maxn=-1;
	for(int i=1;i<=n;i++)
		maxn=max(p[i]+get_best(n-i),maxn);
	r[n]=maxn;
	return maxn;
}

  此外,还可以通过自底向上的方法求出最优解,此时为递推操作,不需要递归

int get_best2(int n)
{
	for(int i=1;i<=n;i++)
	{
		r[i]=p[i]; // 直接将 长度为 i的切割下 
		for(int j=1;j<i;j++)
			r[i]=max(r[i],p[j]+r[i-j]); //免去递归操作 
	}
 } 

         重构解

        将最优解的切割方案求出

int get_best2(int n)
{
	for(int i=1;i<=n;i++)
	{
		r[i]=p[i]; // 直接将 长度为 i的切割下 
		s[i]=i;
		for(int j=1;j<i;j++)
		if(r[i]<p[j]+r[i-j])  //免去递归操作 
		{
			r[i]=p[j]+r[i-j];
			s[i]=j;  // 表示当长度为i时,将切割长度为j的钢条 ,剩余 i-j 已经求出最优解和切割方案了 
		}
	}
	int x=n;
	while(x>0)
	{
		printf("%d ",s[x]);
		x-=s[x];
	}
}

此过程只需在求解规模为 i 的子问题时将,第一段钢条的最优切割长度j保存在 s [ i ] 中

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Oracle使用内部包自定义创建表空间和用户

如果之前有类似的表空间,可以使用dbms自动生成对应的表空间和数据文件 select dbms_metadata.get_ddl(TABLESPACE,ts.tablespace_name) from dba_tablespaces ts; 可以使用类似的 SQL> set echo off SQL> spool /data/logs/create_tablespace.log SQL> select dbms…

Mimics21软件学习总结

一. Mimics21软件安装过程 ① 解压下载好的Mimics软件包&#xff1b; ② 双击“MIS_Medical_21.0.exe”打开等待安装程序初始化完成&#xff1b; ③ 进入安装向导点击“next”&#xff1b; ④ 点击选择“Iaccept the agreement”同意相关协议&#xff0c;随后点击“next”&…

多模态大模型训练数据以及微调数据格式

多模态数据&#xff0c;尤其是中文多模态数据&#xff0c;找一些中文多模态的数据 中文多模态数据集汇总_数据集-阿里云天池本文整理汇总了业界常用的多模态中文数据集&#xff0c;提供了每个数据集的简介、官网、下载地址、Github代码等信息&#xff0c;方便算法研究人员学习…

虚假新闻检测——Adapting Fake News Detection to the Era of Large Language Models

论文地址&#xff1a;https://arxiv.org/abs/2311.04917 1.概论 尽管大量的研究致力于虚假新闻检测&#xff0c;这些研究普遍存在两大局限性&#xff1a;其一&#xff0c;它们往往默认所有新闻文本均出自人类之手&#xff0c;忽略了机器深度改写乃至生成的真实新闻日益增长的现…

Etsy多账号关联怎么办?Etsy店铺防关联解决方法

Etsy虽然相对于其他跨境电商平台来说比较小众&#xff0c;但因为平台是以卖手工艺品为主的&#xff0c;所以成本较低&#xff0c;利润很高。许多跨境卖家都纷纷入驻&#xff0c;导致平台规则越发严格&#xff0c;操作不当就会封号&#xff0c;比如一个卖家操作多个账号会出现关…

国外问卷调查如何做?需要借助海外住宅IP吗?

在数字化时代&#xff0c;国外问卷调查不仅是了解市场需求的重要手段&#xff0c;还成为了一项能够赚取额外收入的方式。随着全球范围内消费者行为的多样化&#xff0c;各类企业和机构越来越需要了解不同地区的用户观点和偏好&#xff0c;以优化产品和服务。 一、国外问卷调查…

Flask中的JWT认证构建安全的用户身份验证系统

&#x1f47d;发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 Flask中的JWT认证&#xff1a;构建安全的用户身份验证系统 随着Web应用程序的发展&#xf…

Linux给磁盘扩容(LVM方式)

Linux给磁盘扩容&#xff08;LVM方式&#xff09; 最近测试性能&#xff0c;在本地打数据时&#xff0c;发现磁盘空间不足&#xff0c;于是想手动给/挂载点添加空间。这里介绍通过LVM方式快速给磁盘扩容。 LVM:是一种技术&#xff0c;方便管理磁盘。如果不用LVM&#xff0c;那…

js的算法-交换排序(快速排序)

快速排序 基本思想 快速排序的基本思想是基于分治法的&#xff1a;在待排序表L【1...n】中任意取一个元素p 作为枢轴&#xff08;或基准&#xff0c;通常取首元素&#xff09;。通过一趟排序将待排序表划分为独立的两部分L【1...k-1】和L【k1...n】;这样的话&#xff0c;L【1…

Linux下的基本指令

基本指令 前言ls 指令语法功能常用选项举例注意关于拼接关于 -a关于文件ls与/的联用ls与根目录ls与任意文件夹ls与常用选项与路径 pwd命令语法功能常用选项注意window与Linux文件路径的区别 cd 指令语法功能举例注意cd路径... touch指令语法功能常用选项 mkdir指令语法功能常用…

【RAG 论文】Query2doc — 使用 LLM 做 Query Expansion 来提高信息检索能力

论文&#xff1a;Query2doc: Query Expansion with Large Language Models ⭐⭐⭐⭐⭐ Microsoft Research, EMNLP 2023 文章目录 背景介绍Query2doc 论文速读实现细节实验结果和分析总结分析 背景介绍 信息检索&#xff08;Information Retrieval&#xff0c;IR&#xff09;指…

如何操作HTTP返回头-ApiHug小技巧-002

&#x1f917; ApiHug {Postman|Swagger|Api...} 快↑ 准√ 省↓ GitHub - apihug/apihug.com: All abou the Apihug apihug.com: 有爱&#xff0c;有温度&#xff0c;有质量&#xff0c;有信任ApiHug - API design Copilot - IntelliJ IDEs Plugin | Marketplace &…

如何用微信小程序实现远程控制无人售货柜

如何用微信小程序实现远程控制无人售货柜呢&#xff1f; 本文描述了使用微信小程序调用HTTP接口&#xff0c;实现控制无人售货柜&#xff0c;独立控制售货柜、格子柜的柜门。 可选用产品&#xff1a;可根据实际场景需求&#xff0c;选择对应的规格 序号设备名称厂商1智能WiFi…

【Canvas与艺术】绘制金色八卦图

【关键点】 等比例缩放各部件及将八卦转为“二进制”的过程。 【成图】 【代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head><title>使用…

gcc make makefile cmake之间的关系梳理

gcc是GNU Compiler Collection&#xff08;GNU编译器套件&#xff09;&#xff0c;也可以简单认为是编译器&#xff0c;它可以编译很多编程语言&#xff08;包括C、C、Object-C、Fortran、Java等&#xff09;当你的程序只有一个源文件&#xff0c;直接用gcc命令编译它。但是当你…

【Java--数据结构】提升你的编程段位:泛型入门指南,一看就会!

前言 泛型是一种编程概念&#xff0c;它允许我们编写可以适用于多种数据类型的代码。通过使用泛型&#xff0c;我们可以在编译时期将具体的数据类型作为参数传递给代码&#xff0c;从而实现代码的复用和灵活性。 在传统的编程中&#xff0c;我们通常需要为不同的数据类型编写不…

总结一下背包里的顺序和是否逆序

1.对于01背包而言&#xff0c;一维压缩态只能物品到背包且需要逆序 2.对应多重背包而言&#xff0c;组合数物品到背包&#xff0c;排列数背包到物品&#xff0c;且都需要正序

【北京迅为】《iTOP-3588开发板系统编程手册》-第20章 socket 应用编程

RK3588是一款低功耗、高性能的处理器&#xff0c;适用于基于arm的PC和Edge计算设备、个人移动互联网设备等数字多媒体应用&#xff0c;RK3588支持8K视频编解码&#xff0c;内置GPU可以完全兼容OpenGLES 1.1、2.0和3.2。RK3588引入了新一代完全基于硬件的最大4800万像素ISP&…

Mudem,打造私密安全、高效稳定的私人空间

Mudem 是 Codigger 平台中的一个关键组件&#xff0c;它提供基础通讯服务&#xff0c;确保不同类型的机器之间可以进行安全和高效的连接。它其设计理念在于将本地机器、公有云以及私有云上的设备无缝地整合为一个可远程在线访问的工作站&#xff08;Workstation&#xff09;。这…

UE4_常见动画节点学习_Two Bone IK双骨骼IK

学习资料&#xff0c;仅供参考&#xff01; Two Bone IK 控制器将逆运动&#xff08;IK&#xff09;解算器应用于到如角色四肢等3关节链。 变量&#xff08; HandIKWeight &#xff09;被用于在角色的 hand_l 和 hand_r 控制器上驱动 关节目标位置&#xff08;Joint Target Lo…