算法导论——动态规划:钢条切割

算法导论——动态规划:钢条切割

package org.loda.dynamic; import org.junit.Test; /** * * @ClassName: RodCutting * @Description: 钢条切割 * * 动态规划问题 * * 给定一段长度为n英寸的钢条和一个价格表Pi,求切割钢条的方案,使得销售收益Rn最大 * * @author minjun * @date 2015年5月17日 下午12:54:46 * */ public class RodCutting { /** * 记录所有价格表 */ private int[] p={1,5,8,9,10,17,17,20,24,30}; //存储之前计算的最优价钱,初始值默认为0 private int[] r; //存储最优价钱时所切割的第一段的长度 private int[] s; @Test public void cutting(){ int n=8; long start=System.nanoTime(); cutting(n); System.out.println("长度为"+n+"英寸切割的最大收益为"+r[n]); System.out.println("切割的两段分别为:"+s[n]+","+(n-s[n])); long end=System.nanoTime(); System.out.println("时间消耗:"+(end-start)/1000000.0+"毫秒"); } private void cutting(int n) { r=new int[n+1]; s=new int[n+1]; //记录第一段切割长度为i时计算过程的数值 for(int i=1;i<=n;i++){ //假设第一段切割长度为i的最大收益为max,为它取个哨兵量的值,即为最小整数 int max=Integer.MIN_VALUE; //不断切割以尝试获取最大收益 for(int j=1;j<=i;j++){ //本次切割后收益更多,就取为本次切割的收益为最大收益,并将本次切割的第一段的长度设为最优切割长度 if(max<p[j-1]+r[i-j]){ max=p[j-1]+r[i-j]; s[i]=j; } } //完成所有的切割尝试之后,会统计出最优的切割方案所获取的收益,将该收益记录为长度n的最优收益 r[i]=max; } } }

输出结果为:

长度为8英寸切割的最大收益为22 切割的两段分别为:2,6 时间消耗:0.386708毫秒

转载于:https://my.oschina.net/u/1378920/blog/415989

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/109450.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • PCA9685–16路 PWM模块舵机驱动板–STM32 IIC接口模块[通俗易懂]

    PCA9685–16路 PWM模块舵机驱动板–STM32 IIC接口模块[通俗易懂]目录一、概述和硬件1、概述2、硬件1、电压2、i2c地址3、使能脚二、寄存器功能 MODE1寄存器外面调用的接口  PCA9685是一款基于IIC总线通信的12位精度16通道PWM波输出的芯片,该芯片最初由NXP推出时主要面向LED开关调光,16路12位PWM信号发生器,可用于控制舵机、led、电机等设备,i2c通信,节省主机资源。就是想控制好几…

  • 茂名天源石化有限责任公司_茂名石化为什么在茂名

    茂名天源石化有限责任公司_茂名石化为什么在茂名目前来看,广东省已经拥有诸多国外化工巨头、大型民营炼化企业和不少国企的炼化项目,成为很多石化企业首选的项目落地基地。“石化业高质量发展看广东”,已经逐渐明朗。今年以来,已有恒力石化(惠州)PTA项目、东华能源(茂名)烷烃资源综合利用项目(一期)、茂名天源石化碳三碳四资源利用等项目开工今年3月31日,广东省发展改革委官网公布《广东省2021年重点建设项目计划》。在2021年重点项目名单中,广东共安排省重点项目1395个,总投资达7.28万亿元,年度计划投资8000亿元。其中新开工项目有3个,总投资约2

    2022年10月16日
  • pycharm激活码2021年2月【2021免费激活】[通俗易懂]

    (pycharm激活码2021年2月)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html83…

  • dpkg用法详解_dpkg -l

    dpkg用法详解_dpkg -ldpkg是一个Debian的一个命令行工具,它可以用来安装、删除、构建和管理Debian的软件包。下面是它的一些命令解释:1)安装软件命令行:dpkg-i示例:dpkg-iavg71flm_r28-1_i386.deb2)安装一个目录下面所有的软件包命令行:dpkg-R示例:dpkg-R/usr/local/src3)释放软件包,但是不进行配置命令

  • idm+百度下载助手解决百度网盘限速

    idm+百度下载助手解决百度网盘限速一.idm下载安装(博主预先安装chrome浏览器)InternetDownloadManager支持所有流行的浏览器,包括:MicrosoftInternetExplorer,Netscape,MSNExplorer,AOL,Opera,Mozilla,MozillaFirefox,MozillaFirebird,AvantBrowser,MyIE2,…

  • html网页设计作业成品(用css和div制作网站)

    话不多说,直接上效果图:历史介绍行政区划:地理环境著名景点:美食小吃工艺品联系我们部分项目结构老师要求的十几个页面20几张图片以及一些跳转,使用div+css布局也基本上都有了。然后代码也有注释。也能够容易看得懂部分代码偷个懒,就用notepad打开。不用H-build打开了。哈哈哈另外有同学要是需要源码的话可以联系我呀。大家加油!奥利给!…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号