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

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

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)


相关推荐

  • U盘安装window系统[通俗易懂]

    U盘安装window系统[通俗易懂]U盘安装window系统:1.制作系统启动U盘,推荐使用老毛桃。2.电脑上插入U盘,启动系统,选择U盘启动。3.进入老毛桃选择界面,选择生成PE系统。推荐win8,之前在一个戴尔电脑上使用win

  • 《抓住听众心理——演讲者要知道的100件事》一第 1 章 人们是怎样思考和学习的…

    《抓住听众心理——演讲者要知道的100件事》一第 1 章 人们是怎样思考和学习的…本节书摘来异步社区《抓住听众心理——演讲者要知道的100件事》一书中的第1章,第1.1节,作者:【美】SusanM.Weinschenk译者:杨妩霞,杨煜泳责编:赵轩,更多章节内容可以访问云栖社区“异步社区”公众号查看。第1章 人们是怎样思考和学习的抓住听众心理——演讲者要知道的100件事“我从来没有‘教导’过我的学生;我只是尝…

  • 关于python的论文参考文献_java毕业论文参考文献

    关于python的论文参考文献_java毕业论文参考文献java论文参考文献英文时间:2015-06-12来源:未知本文字数:14132字作者:小韩单位:在写java毕业论文或高水平java学术论文时,要求参考一些java英文参考文献,外文文献一般体现了国际最新研究进展,让我们写的java论文与国际接轨,为了方便大家,这里学术堂整理了150篇Java论文参考文献英文。更多2020年最新java论文参考文献英文,请在文章末尾处查看。java论文参考…

  • dropna无效_drop from

    dropna无效_drop from需要加等号如df22=df22.dropna(how=”any”)

  • vc++菜鸟教程_vc6.0使用教程详解

    vc++菜鸟教程_vc6.0使用教程详解怎样编写自己的VCL控件     用过Delphi的朋友们,大概对Delphi的最喜欢Delphi的不是他的强类型的pascal语法,而是强大的VCL控件,本人就是一位VCL控件的爱好者。    VCL控件的开源,给我们带来了享之不尽的好处。不像以前的ole控件以及ActiveX,你完全可以重写Delphhi标准控件,而且网上这方面的资源很多。    关于如何编写VCL控件,和多Delphi

  • QT之Android下获取手机传感器数据学习笔记

    QT之Android下获取手机传感器数据学习笔记QT+=coreguisensorspositioning其中sensors是获取手机上传感器数据的组件,positioning是获取位置信息的组件1、获取陀螺仪传感器数据#include&lt;QGyroscope&gt;QGyroscope*gyroscope;QGyroscopeReading*reader;gyroscope=newQGyro…

发表回复

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

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