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

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

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

钢条切割

    问题描述: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
过去的经历必定留下无痕的印记!

推荐标签 标签

  • HTML

    HTML5 是 HTML 下一个的主要修订版本,现在仍处于发展阶段。广义论及 HTML5 时,实际指的是包括 HTML、CSS 和 JavaScript 在内的一套技术组合。

    103 引用 • 294 回帖
  • Swagger

    Swagger 是一款非常流行的 API 开发工具,它遵循 OpenAPI Specification(这是一种通用的、和编程语言无关的 API 描述规范)。Swagger 贯穿整个 API 生命周期,如 API 的设计、编写文档、测试和部署。

    26 引用 • 35 回帖 • 7 关注
  • Hibernate

    Hibernate 是一个开放源代码的对象关系映射框架,它对 JDBC 进行了非常轻量级的对象封装,使得 Java 程序员可以随心所欲的使用对象编程思维来操纵数据库。

    39 引用 • 103 回帖 • 676 关注
  • Ngui

    Ngui 是一个 GUI 的排版显示引擎和跨平台的 GUI 应用程序开发框架,基于
    Node.js / OpenGL。目标是在此基础上开发 GUI 应用程序可拥有开发 WEB 应用般简单与速度同时兼顾 Native 应用程序的性能与体验。

    7 引用 • 9 回帖 • 339 关注
  • 反馈

    Communication channel for makers and users.

    123 引用 • 906 回帖 • 177 关注
  • CentOS

    CentOS(Community Enterprise Operating System)是 Linux 发行版之一,它是来自于 Red Hat Enterprise Linux 依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码,因此有些要求高度稳定的服务器以 CentOS 替代商业版的 Red Hat Enterprise Linux 使用。两者的不同在于 CentOS 并不包含封闭源代码软件。

    238 引用 • 224 回帖
  • 分享

    有什么新发现就分享给大家吧!

    240 引用 • 1729 回帖
  • 服务器

    服务器,也称伺服器,是提供计算服务的设备。由于服务器需要响应服务请求,并进行处理,因此一般来说服务器应具备承担服务并且保障服务的能力。

    124 引用 • 580 回帖
  • DevOps

    DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。

    37 引用 • 24 回帖 • 1 关注
  • OpenResty

    OpenResty 是一个基于 NGINX 与 Lua 的高性能 Web 平台,其内部集成了大量精良的 Lua 库、第三方模块以及大多数的依赖项。用于方便地搭建能够处理超高并发、扩展性极高的动态 Web 应用、Web 服务和动态网关。

    17 引用 • 41 关注
  • Laravel

    Laravel 是一套简洁、优雅的 PHP Web 开发框架。它采用 MVC 设计,是一款崇尚开发效率的全栈框架。

    19 引用 • 22 回帖 • 675 关注
  • 职场

    找到自己的位置,萌新烦恼少。

    126 引用 • 1699 回帖
  • 设计模式

    设计模式(Design pattern)代表了最佳的实践,通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。

    198 引用 • 120 回帖
  • Spark

    Spark 是 UC Berkeley AMP lab 所开源的类 Hadoop MapReduce 的通用并行框架。Spark 拥有 Hadoop MapReduce 所具有的优点;但不同于 MapReduce 的是 Job 中间输出结果可以保存在内存中,从而不再需要读写 HDFS,因此 Spark 能更好地适用于数据挖掘与机器学习等需要迭代的 MapReduce 的算法。

    74 引用 • 46 回帖 • 549 关注
  • 30Seconds

    📙 前端知识精选集,包含 HTML、CSS、JavaScript、React、Node、安全等方面,每天仅需 30 秒。

    • 精选常见面试题,帮助您准备下一次面试
    • 精选常见交互,帮助您拥有简洁酷炫的站点
    • 精选有用的 React 片段,帮助你获取最佳实践
    • 精选常见代码集,帮助您提高打码效率
    • 整理前端界的最新资讯,邀您一同探索新世界
    488 引用 • 383 回帖
  • CodeMirror
    1 引用 • 2 回帖 • 108 关注
  • 钉钉

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

    15 引用 • 67 回帖 • 380 关注
  • ReactiveX

    ReactiveX 是一个专注于异步编程与控制可观察数据(或者事件)流的 API。它组合了观察者模式,迭代器模式和函数式编程的优秀思想。

    1 引用 • 2 回帖 • 124 关注
  • 创造

    你创造的作品可能会帮助到很多人,如果是开源项目的话就更赞了!

    171 引用 • 988 回帖
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    10 引用 • 54 回帖 • 125 关注
  • Telegram

    Telegram 是一个非盈利性、基于云端的即时消息服务。它提供了支持各大操作系统平台的开源的客户端,也提供了很多强大的 APIs 给开发者创建自己的客户端和机器人。

    5 引用 • 35 回帖 • 2 关注
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    529 引用 • 3527 回帖 • 1 关注
  • 星云链

    星云链是一个开源公链,业内简单的将其称为区块链上的谷歌。其实它不仅仅是区块链搜索引擎,一个公链的所有功能,它基本都有,比如你可以用它来开发部署你的去中心化的 APP,你可以在上面编写智能合约,发送交易等等。3 分钟快速接入星云链 (NAS) 测试网

    3 引用 • 16 回帖 • 2 关注
  • Sphinx

    Sphinx 是一个基于 SQL 的全文检索引擎,可以结合 MySQL、PostgreSQL 做全文搜索,它可以提供比数据库本身更专业的搜索功能,使得应用程序更容易实现专业化的全文检索。

    1 引用 • 171 关注
  • 七牛云

    七牛云是国内领先的企业级公有云服务商,致力于打造以数据为核心的场景化 PaaS 服务。围绕富媒体场景,七牛先后推出了对象存储,融合 CDN 加速,数据通用处理,内容反垃圾服务,以及直播云服务等。

    25 引用 • 215 回帖 • 161 关注
  • 小薇

    小薇是一个用 Java 写的 QQ 聊天机器人 Web 服务,可以用于社群互动。

    由于 Smart QQ 从 2019 年 1 月 1 日起停止服务,所以该项目也已经停止维护了!

    34 引用 • 467 回帖 • 689 关注
  • OkHttp

    OkHttp 是一款 HTTP & HTTP/2 客户端库,专为 Android 和 Java 应用打造。

    16 引用 • 6 回帖 • 56 关注