算法导论--第15章 动态规划--钢条切割

2024-05-24 22:32

本文主要是介绍算法导论--第15章 动态规划--钢条切割,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法导论

--第15章 动态规划

动态规划:通过组合子问题的解来求解原问题,应用于子问题重叠的情况,即不同的子问题具有公共的子子问题。

设计动态规划算法的步骤:

①   刻画一个最优解的结构特征。

②   递归定义最优解的值。

③   计算最优解的值,通常采用自底向上的方法。

④   利用计算处的信息构造一个最优解。

 

 

15.1 钢条切割

 钢条切割问题:给定一段长度为n英寸的钢条和一个价格表 (i=1,2, …,n),求切割钢条的方案,使得销售收益 最大。注意,如果长度为n英寸的钢条价格  足够大,最饥饿可能就是完全不需要切割。

若钢条的长度为i,则钢条的价格为Pi,如何对给定长度的钢条进行切割能得到最大收益?

长度i    1    2    3   4     5      6      7     8      9      10

价格Pi    1    5    8   9     10    17   17   20    14    30

 

i = 1时,钢条不可切割,r[1]= 1

i = 2时,钢条可分割为1+ 1,其价格为2。若不分割(0 + 2),价格为5。即r[2] = 5

i = 3时,钢条可分割为0+ 3, 1 + 2。r[3] = 8

同理可得:

r[4] = 10(2+ 2)

r[5] = 13(2+ 3)

r[6] = 17(0+ 6)

r[7] = 18(1+ 6或4+ 3=> 2 + 2 + 3

.......

 

我们可以发现,长度为7时,将其切割为长度4与长度3的钢条,并对两个钢条分别求最优解:长度4的最优解为r[4] = 10(2 + 2),长度3的最优解为r[3] = 8,即可得r[7] =r[4]+ r[3] =>原问题的最优解等于子问题的最优解之和的最大值

 我们将钢条左边切割下长度为 i 的一段,只对右边剩下的长度为 n-i 的一段继续进行切割(递归求解),对左边的一段不再进行切割。即问题分解的方式为:将长度为n 的钢条分解为左边开始一段,以及剩余部分继续分解的结果。这样,不做任何切割的方案就可以描述为:第一段的长度为n ,收益为 pn,剩余部分长度为0,对应的收益为r0=0。于是公式的简化版本:

因此,在计算r[i]时,所求值即为r[0] +r[i],r[1]+ r[i- 1],r[2]+ r[i- 2],...  ,r[i- 1] +r[1] 之间的最大值,而在动态规划中,r[0]——r[i - 1]的值在计算r[i]之前已经保存好了,进行少量的运算便能取得最优结果。

codes:

#include<iostream>
#include<cstring>
using namespace std;
int p[1000],r[1000],s[1000];
void cut_rod(int* a,int b)
{r[0]=0;for(int i=1;i<=b;i++){int q=-1e8;for(int j=1;j<=i;j++){if(q<(a[j]+r[i-j])){q=a[j]+r[i-j];s[i]=j;r[i]=q;}}}cout<<r[b]<<endl<<s[b]<<endl;
}
int main()
{int n;cin>>n;memset(p,0,sizeof(p));memset(r,0,sizeof(r));memset(s,0,sizeof(s));for(int i=1;i<=n;i++)cin>>p[i];cut_rod(p,n);return 0;
}


这篇关于算法导论--第15章 动态规划--钢条切割的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Python Selenium动态渲染页面和抓取的使用指南

《PythonSelenium动态渲染页面和抓取的使用指南》在Web数据采集领域,动态渲染页面已成为现代网站的主流形式,本文将从技术原理,环境配置,核心功能系统讲解Selenium在Python动态... 目录一、Selenium技术架构解析二、环境搭建与基础配置1. 组件安装2. 驱动配置3. 基础操作模

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

慢sql提前分析预警和动态sql替换-Mybatis-SQL

《慢sql提前分析预警和动态sql替换-Mybatis-SQL》为防止慢SQL问题而开发的MyBatis组件,该组件能够在开发、测试阶段自动分析SQL语句,并在出现慢SQL问题时通过Ducc配置实现动... 目录背景解决思路开源方案调研设计方案详细设计使用方法1、引入依赖jar包2、配置组件XML3、核心配

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n