文档章节

动态规划 ———— 钢条切割到底在切啥?

木兰宿莽
 木兰宿莽
发布于 2017/02/26 22:19
字数 1161
阅读 131
收藏 1

      暂先不看问题本身,先来了解一下什么叫动态规划。从英文的dynamic programming来看似乎并没有“规划”的意思在里边。但是,这里的programming并非指的是编程,而是指的一种表格法,这种表格法旨在一步步详细分解问题,使之细化并最终获得问题的解。所以我们称之为“规划”。

       动态规划和分治法类似,都是将大问题分解成小的子问题。但分治法本身的小问题往往是独立的,而动态规划的小的子问题依赖于大问题。

       动态规划方法通常用来求解最优化问题(optimization problem)。这类问题通常可以有很多个解,例如钢条切割可以有很多中切割方法同样达到最大收益。

通常按如下4个步骤设计一个动态规划算法:
1. 刻画一个最优解的结构特征。
2. 递归定义最优解的值
3. 计算最优解的值,通常采用自底向上的方法。
4. 利用计算出的信息构造一个最优解。
 

长度为n英寸的钢条共有2^n-1种不同的方法(这里认为对称切割属于不同的方法)。


这里以n = 9 为例,则总共有256种切割方案。

分别查看几种方案:

第一种:

 收益: 1 + 20 = 21

第二种:

收益: 10 + 10 = 20 比第一种少1

第三种:

收益: 1 * 9 = 9 显然是收益最少的

综合来看,收益最大的应该是 17 + 8 = 25,即分成6和3

 

算法实现:

1. 自顶向下递归实现

2. 带备忘的自顶向下法

3. 自底向上法

 


几种方法的比较:
        切钢条只是一个引子,切的过程就是对应动态规划的不同的规模下子问题的求解过程。用不用递归并不是动态规划的本质。递归只是一种方法或者工具,而不是一种思想。自底向上的方法就没有用到函数递归。
        朴素的递归算法之所以效率很低,是因为它反复求解相同的子问题。比方长度为33的钢条可以有2^32 = 4294967296种切割方法。用朴素的递归方法,需要求解这么大的一个规模,且不说频繁调用函数所产生的花销,要计算10亿次以上的加法和比较,这本身就很消耗时间。
        基于此,动态规划方法仔细地安排求解顺序,对每一个子问题都只求解一次,并将值保存起来。如果之后再有求此子问题便可以查询其值而不是重新再求一遍。带备忘的动态规划法需要额外的内存开销,但是节省的时间却是可观的:可能将一个指数时间的解转化为多项式时间的解。

C++代码实现:

#include<iostream>
#include<climits>
#include<ctime>
#include<cstdlib>
int price[] = {1,5,8,9,10,17,17,20,24,30,32,33,33,39,41,44,45,45,45,48,50,55,60,70,78,79,79,88,90,91,92,92,92};

int max(int a,int b)
{
   return a>b?a:b;
}

int cut_rod(int p[],int n)
{
  if(n == 0) return 0;
   
  int q = INT_MIN;
  
  for(int i = 1; i <= n; i++){
    q = max(q,p[i-1] + cut_rod(p,n-i));
  }
return q;
}

int cut_rod_memoized(int p[],int n,int r[])
{
   if(r[n-1] >= 0) return r[n-1];
   int q;
   if(n == 0){
      q = 0;
   }
   else{
      q = INT_MIN;
   }
   for(int i=1;i <= n; i++)
      q = max(q,p[i-1]+cut_rod_memoized(p,n-i,r));
r[n-1] = q;
return q;
}

int cut_rod_memoized_core(int p[],int n)
{
   int r[n];
   for(int i=0;i < n;i++){
     r[i] = INT_MIN;
   }
return cut_rod_memoized(p,n,r);
}

int bottom_up_cut_rod(int p[],int n)
{
   int r[n];
   
  
   for(int j = 1;j <= n; j++){
     int q = INT_MIN;
     for(int i = 1; i <= j; i++){
       if(j-1 -i >= 0){
         q = max(q,p[i-1] + r[j-1 - i]);
       } 
       else{
         q = max(q,p[i-1]);
       }
     }
     r[j-1] = q;
   }
return r[n-1];
}


int main(int argc,char* argv[])
{
   if(argc != 2) return -1;
   time_t start_time = time(NULL);
   int condition = atoi(argv[1]);
   switch(condition){
       case 0:std::cout<<cut_rod(price,sizeof(price)/sizeof(int))<<std::endl; break;
       case 1:std::cout<<cut_rod_memoized_core(price,sizeof(price)/sizeof(int))<<std::endl; break;
       case 2:std::cout<<bottom_up_cut_rod(price,sizeof(price)/sizeof(int))<<std::endl; break;
       default:break;
   }
   time_t end_time   = time(NULL);
   std::cout<<"use:"<<end_time-start_time<<"seconds"<<std::endl;
return 0;
}

单纯的递归实现需要大概100秒的时间才能算出来,而另两种只需要不到1秒时间。这就可以看出动态规划的威力了。

© 著作权归作者所有

共有 人打赏支持
木兰宿莽
粉丝 35
博文 12
码字总数 8250
作品 0
崇明
程序员
【动态规划】初识,钢条切割问题

正文之前 其实动态规划老早之前就看过, 但是可惜的是印象不深,到今天彻底忘得差不多了,这两天看《算法导论》终于让我啃下了二叉搜索树和红黑树两个家伙,虽然还未曾熟练于胸,但是基本能用...

HustWolf
07/18
0
0
经典动态规划题若干

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,...

樂天
2016/01/22
54
0
太全了!慢走丝线切割加工中常见问题及解决方法

     一、断丝   1.放电状态不佳——降低 P 值,如果 P 值降低幅度较大仍断丝,可考虑降低 I 值,直至不断丝。此操作会降低加工效率,如果频繁断丝,请参考以下内容,找出导致断丝的根...

UG数控编程
01/04
0
0
解决最优子结构问题的两种方法----动态规划和贪心算法

1、两种重要算法思想: 动态规划,贪心算法 2、动态规划: 基本原理:动态规划英文名dynamic programming。其中pogramming指的是表格法,而非编写计算机程序。因此,可以初步得出动态规划的基...

thoresa
2015/05/18
0
0
动态规划法(一)从斐波那契数列谈起

动态规划法与分治方法   动态规划(Dynamic Programming)与分治方法相似,都是通过组合子问题的解来求解原问题。不同的是,分治方法通常将问题划分为互不相交的子问题,递归地求解子问题,...

jclian91
05/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

React 服务器渲染原理解析与实践

网盘下载地址 React 服务器渲染原理解析与实践 本套课程,讲解了React中SSR技术的整个搭建思路及流程,完整的从原理上讲清楚了SSR的概念,重点在于讲解编写SSR框架遇到的各种知识点,以及细节...

qq__2304636824
34分钟前
0
0
sourcetree 离线免注册登录安装教程

Sourcetree是一个优秀的git可视化管理工具,深受开发者喜爱Sourcetree官网,但是在安装时需要谷歌账户登录,需要翻qiang才可以,此一点一直被人们所诟病。今天本教程就为大家提供离线免登陆安...

QQZZFT
今天
1
0
使用 PostgreSQL 解决一个实际的统计分析问题

使用 PostgreSQL 解决一个实际的统计分析问题作者:老农民(刘启华)Email: 46715422@qq.com 之前有个朋友扔给我一个奇葩需求,他们公司之前做了一批问卷调查,全部都是统一格式的excel...

新疆老农民
今天
8
0
TypeScript基础入门之高级类型的映射类型

转发 TypeScript基础入门之高级类型的映射类型 高级类型 映射类型 一个常见的任务是将一个已知的类型每个属性都变为可选的: interface PersonPartial {    name?: string;    age?...

durban
今天
1
0
Dubbo源码分析(6):Dubbo内核实现之基于SPI思想Dubbo内核实现

SPI接口定义 定义了@SPI注解 package com.alibaba.dubbo.common.extension; import java.lang.annotation.Documented;import java.lang.annotation.ElementType;import java.lang.an......

郑加威
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部