切割钢条【动态规划】

2024-06-15 05:58
文章标签 动态 规划 切割 钢条

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

假设公司出售一段长度为i英寸的钢条的价格为Pi(i = 1, 2, ...单位:美元),下面给出了

价格表样例:

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

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


切割钢条的问题是这样的:给定一段长度为n英寸的钢条和一个价格表Pi,求切割方案,使

得销售收益Rn最大。当然,如果长度为n英寸的钢条价格Pn足够大,最优解可能就是完全

不需要切割。对于上述价格表样例,我们可以观察所有最优收益值Ri及对应的最优解方案:

R1 = 1,切割方案1 = 1(无切割)
R2 = 5,切割方案2 = 2(无切割)
R3 = 8, 切割方案3 = 3(无切割)
R4 = 10, 切割方案4 = 2 + 2
R5 = 13, 切割方案5 = 2 + 3
R6 = 17, 切割方案6 = 6(无切割)
R7 = 18, 切割方案7 = 1 + 6或7 = 2 + 2 + 3
R8 = 22, 切割方案8 = 2 + 6
R9 = 25, 切割方案9 = 3 + 6
R10 = 30,切割方案10 = 10(无切割)
更一般地,对于Rn(n >= 1),我们可以用更短的钢条的最优切割收益来描述它:
Rn = max(Pn, R1 + Rn-1, R2 + Rn-2,...,Rn-1 + R1) 公式I
首先将钢条切割为长度为i和n - i两段,接着求解这两段的最优切割收益Ri和Rn - i
(每种方案的最优收益为两段的最优收益之和),由于无法预知哪种方案会获得最优收益,

我们必须考察所有可能的i,选取其中收益最大者。如果直接出售原钢条会获得最大收益,我

们当然可以选择不做任何切割。

//带备忘的自顶向下法
#include<stdio.h>
#include<algorithm>
using namespace std;
const int INF = 0xffffff0;
int p[110],r[110];int MEMOIZED_CUT_ROD_AUX(int n)
{if(r[n] >= 0)//检查所求值是否是已知的return r[n];int q;if(n == 0)//这里计算局部最优解q = 0;else{q = -INF;for(int i = 1;i <= n; i++)q = max(q,p[i]+MEMOIZED_CUT_ROD_AUX(n-i));}r[n] = q;//将q存入r[n],返回q值return q;
}
int MEMOIZED_CUT_ROD(int n)
{int i;for(i = 0; i <= n; i++)//全部初始化r[i] = -INF;return MEMOIZED_CUT_ROD_AUX(n);//求解
}int main()
{int N;while(~scanf("%d",&N)){for(int i = 1; i <= N; i++)scanf("%d",&p[i]);int ans = MEMOIZED_CUT_ROD(N);printf("%d\n",ans);}return 0;
}

钢条切割问题还存在一种相似的但更为简单的地柜求解方法:

我们将钢条从左边切割下长度为i的一段,只对右边剩下长度为n-i的一段惊醒切割。(递归

求解),对左边的一段则不再切割。即问题的分解方式为:将长度为n的钢条分解为左边开

始一段,以及剩余部分继续分解的结果。这样,不做任何切割的方案就可以描述为:第一段

的长度为n,收益为Pn,剩余部分长度为0,对应的收益为R0 = 0。于是我们可以得到公式I

的简化版本:

Rn = max(Pi+Rn-i)(1<=i<=n)  公式II

在此公式中,原问题的最优解只包含一个相关子问题(右端剩余部分)的解,而不是两个。

//自底向上法
#include<stdio.h>
#include<algorithm>
using namespace std;
const int INF = 0xffffff0;
int p[110],r[110];//r[n]来保存子问题int BOTTOM_UP_CUT_ROD(int n)
{r[0] = 0;//长度为0的钢条没有收益for(int j = 1; j <= n; j++)//对j=1,2,3,…,n按升序求解每个规模为j的子问题。{int q = -INF;for(int i = 1; i <= j; i++){q = max(q,p[i]+r[j-i]);//直接访问数组r[j-i]来获得规模为j-i的子问题的解}r[j] = q;}return r[n];
}
int main()
{int N;while(~scanf("%d",&N)){for(int i = 1; i <= N; i++)scanf("%d",&p[i]);int ans = BOTTOM_UP_CUT_ROD(N);printf("%d\n",ans);}return 0;
}





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



http://www.chinasem.cn/article/1062607

相关文章

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题(Topic)的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体(数据库的定义)2.预加载preload3.添加关联的方法一、动态路由1

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

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

慢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)配置类绑定短信发送策略接口示例:阿里云 & 腾

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

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