动态规划法(五)钢条切割问题(rod cutting problem)
继续讲故事~~
我们的主人公现在已经告别了生于斯,长于斯的故乡,来到了全国最大的城市S市。这座S市,位于国家的东南部,是全国的经济中心,工商业极为发达,是这个国家的人民所向往的城市。这个到处都留着奶与蜜的城市,让丁丁充满了好奇感和新鲜感,他多想好好触摸这个城市的脉搏啊!
这不,他此刻正走在城市的某高新园区,不远处传来钢条切割的声音。他好奇地走上前去,看着工人们正在熟练地切割钢条,并打包完成包装。此时,一位工人看到了丁丁,一看,竟是自己的同乡。他热情地上去打了招呼,并询问了乡下的情况,他俩约了中午一起吃饭。
午饭时,老乡热情地请丁丁在园区最好的饭店吃饭,他俩聊得也很开心。突然,老乡想到了丁丁学过计算机方面的理论,于是他准备把自己最近遇到的问题告诉丁丁,看看他能不能解决。
钢条切割问题: 给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,...,n)pi(i=1,2,...,n),求切割钢条方案,使得销售收益RnRn最大。注意,如果长度为n英寸的钢条的价格pnpn足够大,最优解可能就是完全不需要切割。
已知钢条价格表如下:
长度i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
价格pipi | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
听到老乡正在为整个问题发愁,丁丁内心也想着尝试解决这个问题。毫无疑问,这个问题也是可以用动态规划法解决的,于是,他拿出稿纸推演起来:
将钢条从左边切割下长度为i的一段,只对右边剩下的长度为n-i的一段继续进行切割(递归求解),对左边的一段则不再进行切割。这样,不做任何切割的方案可以描述为:第一段长度为n,收益为pn,剩余部分长度为0,对应的收益为R0R0=0。于是,我们就得到该问题的求解公式:
Rn=min1≤i≤n(pn+Rn−1)Rn=min1≤i≤n(pn+Rn−1)
采用自底向上法(bottom-up method)来求解该问题,需要用一个列表来记录收益rnrn,一个列表来记录切割方案,其Python代码如下:
import time # 使用动态规划法(dynamic programming)解决钢条切割问题 # 钢条长度与对应的收益 length = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) profit = (1, 5, 8, 9, 10, 17, 17, 20, 24, 30) # 动态归纳法,自底向上的CUT-ROD过程,加入备忘机制 # 运行时间: 多项式 # 参数:profit: 收益列表, n: 钢条总长度 # 返回参数: q: 最大收益 def bottom_up_cut_rod(profit, n): r = [0] # 收益列表 s = [0]*(n+1) # 切割方案列表 for j in range(1, n+1): q = float('-inf') for i in range(1, j+1): if max(q, profit[length.index(i)]+r[j-i]) == profit[length.index(i)]+r[j-i]: s[j] = i q = max(q, profit[length.index(i)]+r[j-i]) r.append(q) return r[n], s[n] # method of how to cut the rod def rod_cut_method(profit, n): how = [] while n != 0: t,s = bottom_up_cut_rod(profit, n) how.append(s) n -= s return how for i in range(1, 11): t1 = time.time() money,s = bottom_up_cut_rod(profit, i) how = rod_cut_method(profit, i) t2 = time.time() print('profit of %d is %d. Cost time is %ss.'%(i, money, t2-t1)) print('Cut rod method:%s\n'%how)
输出结果:
profit of 1 is 1. Cost time is 0.0s. Cut rod method:[1] profit of 2 is 5. Cost time is 0.0s. Cut rod method:[2] profit of 3 is 8. Cost time is 0.0s. Cut rod method:[3] profit of 4 is 10. Cost time is 0.0s. Cut rod method:[2, 2] profit of 5 is 13. Cost time is 0.0s. Cut rod method:[3, 2] profit of 6 is 17. Cost time is 0.0s. Cut rod method:[6] profit of 7 is 18. Cost time is 0.0s. Cut rod method:[6, 1] profit of 8 is 22. Cost time is 0.0005009174346923828s. Cut rod method:[6, 2] profit of 9 is 25. Cost time is 0.0s. Cut rod method:[6, 3] profit of 10 is 30. Cost time is 0.0s. Cut rod method:[10]
不一会儿他就搞定了这个问题,他将不同长度的钢条所能获得最大收益和对应的切割方案告诉了老乡。老乡听后大喜,他为丁丁解决了这个困扰它们公司长久的问题而感到由衷高兴,有了以上的结果,那么,钢条的长度再长也不是问题了。
午饭后,老乡将刚才吃饭时丁丁的解决方法告诉了老板,老板也是喜出望外,他决定高薪聘请这个年轻人。而我们的丁丁,他早已离开高新区,向着下一个目的地出发了~~
注意:本人现已开通两个微信公众号: 用Python做数学(微信号为:python_math)以及轻松学会Python爬虫(微信号为:easy_web_scrape), 欢迎大家关注哦~~
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Velocity引擎原理探究
一、前言 常见的Java模板引擎有JSP、Freemark,Velocity。在MVC三层框架中,模板引擎属于view层,实质是把model层内容展现到前台页面的一个引擎,velocity以其前后端解耦使前后台可以同时开发和其语法的简易性得到了广泛的应用,集团WebX框架就建议使用它作为模板引擎。 二、原理 2.1 架构介绍 打开velocity的源码包,从代码结构看velocity主要包括app、context、runtime、event、texen和一些util类 1)、app模块 源码org.apache.velocity.app下面主要有两个类Velocity和VelocityEngine。 Velocity ,主要对外提供一些static方法,可以通过类名直接调用,只要通过Velocity创建一个模块,在创建一个存放变量的cont
- 下一篇
C# 登录界面 密码修改
form1: using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; namespace 简单登录界面 { public partial class Form1 : Form { public Form1() { InitializeComponent(); } private void button1_Click(object sender, EventArgs e) { String name = this.textBox1.Text; // 获取里面的值 String password = this.textBox2.Text; if (name.Equals("admin") && password.Equals("admin")) // 判断账号密码是否...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- CentOS关闭SELinux安全模块
- Hadoop3单机部署,实现最简伪集群
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- SpringBoot2全家桶,快速入门学习开发网站教程
- SpringBoot2更换Tomcat为Jetty,小型站点的福音
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- MySQL8.0.19开启GTID主从同步CentOS8
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2整合Redis,开启缓存,提高访问速度