【算法导论】动态规划 - 钢条切割问题

本贴最后更新于 3057 天前,其中的信息可能已经时移世改

    最优子结构和子问题重复定义可以参考算法导论。

钢条切割

    问题描述:Seriling公司购买长钢条,将其切割为短钢条出售。切割工序本身没有成本。公司管理层希望知道最佳切割方案。假定我们知道公司出售一段长度为i 英寸的钢条的价格为pi(i=1,2,3,...,n,单位为美元)。钢条的长度均为整英寸。     

长度i

1

2

3

4

5

6

7

8

9

10

pi

1

5

8

9

10

17

17

20

24

30

 

数学表达式:

对于r(n)(n>=1),总可以用更短的钢条的最优收益切割来描述它: 

                                                        r(n)=max(p(n),r(1)+r(n−1),r(2)+r(n−2)....)                           (1)
p(n)表示不切割,其他n-1个参数对应另外n-1中方案:对每个i=1,2,...n−1,首先将钢条切割为长度为i和n−i的两段,在分别求解这两段的最优切割收益。由于无法预知哪种方案获益最大,因此需要考察每一种方案。 公式(1)化简为
                                                        r(n)=max(p(i)+r(n-i))         ,1<=i<=n                                    (2)                 

实现过程中,主要应用公(2)来计算。

这里直接给出实现的方案:

import java.util.Scanner;

/**
 * Created by Rudy Steiner on 2017/3/28.
 * 算法导论 动态规划-钢条切割问题
 */
public class SteelCutting {
/* 自顶向下,朴素递归切割 * @param p: 收益数组 * @param n: 待切割钢条长度 * */ public static int tDRecursiveCut(int[] p,int n){ System.out.print(n+" "); if(n==0) return 0; int result=Integer.MIN_VALUE; for (int i=0;i&lt;n;i++){ result=Math.max(result,p[i]+tDRecursiveCut(p,n-i-1)); } return result; } /* * 自顶向下,带记忆的切割 top down * @param p: 收益数组 * @param n: 待切割的长度 * @param r: 收益记忆数组 * */ public static int tDRecursiveCutWithMemory(int[] p,int n,int[] r){ if(r[n]&gt;=0){ return r[n]; } System.out.print(n+" "); int result=Integer.MIN_VALUE; if(n==0) result=0; else { for (int i = 0; i &lt; n; i++) { result = Math.max(result, p[i] + tDRecursiveCutWithMemory(p, n - i - 1, r)); } } r[n]=result; return result; } /* * 自底向上,非递归切割 bottom up * @param p: 收益数组 * @param n: 待切割的长度 * @param c: 切割方案 * */ public static int bUNonRecursive(int[] p,int n,int[] c){ int result; int[] r=new int[n+1]; int rn=r.length; r[0]=0; c[0]=0; for(int i=1;i&lt;rn;i++){ result=Integer.MIN_VALUE; for(int j=0;j&lt;i;j++){ if(result&lt;p[j]+r[i-j-1]) { result = p[j] + r[i - j - 1]; c[i]=j+1; } } r[i]=result; } return r[n]; } public static void main(String[] args){ Scanner in=new Scanner(System.in); int n=in.nextInt(); int[] p=new int[n]; for(int i=0; i&lt;n;i++){ p[i]=in.nextInt(); } int toCut=in.nextInt(); int[] r=new int[toCut+1]; int[] c=new int[toCut+1]; for(int i=r.length-1;i&gt;=0;i--){ r[i]=Integer.MIN_VALUE; } int value; //value=tDRecursiveCut(p,toCut); //value=tDRecursiveCutWithMemory(p,toCut,r); value=bUNonRecursive(p,toCut,c); System.out.print("切割方案:"); while(toCut&gt;0){ System.out.print(c[toCut]+" "); toCut=toCut-c[toCut]; } System.out.printf("\r\n最优切割受益:%d,耗时:%d",value,0); }

}


相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • someone

    第一篇关于算法的博客,后续还会写各种算法题解!

waert
过去的经历必定留下无痕的印记!

推荐标签 标签

  • 阿里巴巴

    阿里巴巴网络技术有限公司(简称:阿里巴巴集团)是以曾担任英语教师的马云为首的 18 人,于 1999 年在中国杭州创立,他们相信互联网能够创造公平的竞争环境,让小企业通过创新与科技扩展业务,并在参与国内或全球市场竞争时处于更有利的位置。

    43 引用 • 221 回帖 • 45 关注
  • frp

    frp 是一个可用于内网穿透的高性能的反向代理应用,支持 TCP、UDP、 HTTP 和 HTTPS 协议。

    17 引用 • 7 回帖 • 3 关注
  • 友情链接

    确认过眼神后的灵魂连接,站在链在!

    24 引用 • 373 回帖 • 2 关注
  • Kafka

    Kafka 是一种高吞吐量的分布式发布订阅消息系统,它可以处理消费者规模的网站中的所有动作流数据。 这种动作(网页浏览,搜索和其他用户的行动)是现代系统中许多功能的基础。 这些数据通常是由于吞吐量的要求而通过处理日志和日志聚合来解决。

    36 引用 • 35 回帖
  • Vditor

    Vditor 是一款浏览器端的 Markdown 编辑器,支持所见即所得、即时渲染(类似 Typora)和分屏预览模式。它使用 TypeScript 实现,支持原生 JavaScript、Vue、React 和 Angular。

    378 引用 • 1866 回帖 • 2 关注
  • Sym

    Sym 是一款用 Java 实现的现代化社区(论坛/BBS/社交网络/博客)系统平台。

    下一代的社区系统,为未来而构建

    524 引用 • 4601 回帖 • 709 关注
  • 黑曜石

    黑曜石是一款强大的知识库工具,支持本地 Markdown 文件编辑,支持双向链接和关系图。

    A second brain, for you, forever.

    26 引用 • 264 回帖 • 1 关注
  • QQ

    1999 年 2 月腾讯正式推出“腾讯 QQ”,在线用户由 1999 年的 2 人(马化腾和张志东)到现在已经发展到上亿用户了,在线人数超过一亿,是目前使用最广泛的聊天软件之一。

    45 引用 • 557 回帖 • 1 关注
  • V2EX

    V2EX 是创意工作者们的社区。这里目前汇聚了超过 400,000 名主要来自互联网行业、游戏行业和媒体行业的创意工作者。V2EX 希望能够成为创意工作者们的生活和事业的一部分。

    16 引用 • 236 回帖 • 236 关注
  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    554 引用 • 675 回帖
  • jsDelivr

    jsDelivr 是一个开源的 CDN 服务,可为 npm 包、GitHub 仓库提供免费、快速并且可靠的全球 CDN 加速服务。

    5 引用 • 31 回帖 • 110 关注
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 562 关注
  • Chrome

    Chrome 又称 Google 浏览器,是一个由谷歌公司开发的网页浏览器。该浏览器是基于其他开源软件所编写,包括 WebKit,目标是提升稳定性、速度和安全性,并创造出简单且有效率的使用者界面。

    63 引用 • 289 回帖 • 1 关注
  • 招聘

    哪里都缺人,哪里都不缺人。

    188 引用 • 1057 回帖 • 1 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3203 引用 • 8217 回帖
  • CloudFoundry

    Cloud Foundry 是 VMware 推出的业界第一个开源 PaaS 云平台,它支持多种框架、语言、运行时环境、云平台及应用服务,使开发人员能够在几秒钟内进行应用程序的部署和扩展,无需担心任何基础架构的问题。

    4 引用 • 16 回帖 • 201 关注
  • Latke

    Latke 是一款以 JSON 为主的 Java Web 框架。

    71 引用 • 535 回帖 • 833 关注
  • 音乐

    你听到信仰的声音了么?

    62 引用 • 512 回帖
  • FFmpeg

    FFmpeg 是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序。

    23 引用 • 32 回帖 • 5 关注
  • RemNote
    2 引用 • 16 回帖 • 26 关注
  • 钉钉

    钉钉,专为中国企业打造的免费沟通协同多端平台, 阿里巴巴出品。

    15 引用 • 67 回帖 • 260 关注
  • V2Ray
    1 引用 • 15 回帖 • 4 关注
  • IDEA

    IDEA 全称 IntelliJ IDEA,是一款 Java 语言开发的集成环境,在业界被公认为最好的 Java 开发工具之一。IDEA 是 JetBrains 公司的产品,这家公司总部位于捷克共和国的首都布拉格,开发人员以严谨著称的东欧程序员为主。

    181 引用 • 400 回帖
  • Word
    13 引用 • 41 回帖 • 1 关注
  • 人工智能

    人工智能(Artificial Intelligence)是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门技术科学。

    119 引用 • 323 回帖
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    268 引用 • 666 回帖 • 2 关注
  • Netty

    Netty 是一个基于 NIO 的客户端-服务器编程框架,使用 Netty 可以让你快速、简单地开发出一个可维护、高性能的网络应用,例如实现了某种协议的客户、服务端应用。

    49 引用 • 33 回帖 • 45 关注