文档章节

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

木兰宿莽
 木兰宿莽
发布于 2017/02/26 22:19
字数 1161
阅读 110
收藏 1
点赞 0
评论 0

      暂先不看问题本身,先来了解一下什么叫动态规划。从英文的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秒时间。这就可以看出动态规划的威力了。

© 著作权归作者所有

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

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

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

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

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

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

UG数控编程
01/04
0
0
深度学习微信精选文章

公众号——深度学习每日摘要 所有文章(持续更新中): 聊聊语音识别的发展历程 说说重要的贝叶斯公式吧 我对入门深度学习的切身体会 聊聊隐马尔科夫模型(HMM) 关于防止过拟合的一些想法 ...

断桥残雪断桥残雪
2016/12/02
507
2
怎样衡量两个字符串的相似度(编辑距离动态规划求解)

前言 目前计算句子相似性有很多不同的方案,比如基于语义词典的方法、基于相同词汇的方法、基于统计的方法和基于编辑距离的方法。这篇文章先介绍编辑距离的基础。 编辑距离 编辑距离其实就是...

超人汪小建
06/12
0
0
iPhone 6 / 6 Plus 设计·适配方案

iPhone 6 / 6 Plus 设计·适配方案 关于iPhone6/6+适配问题一直有争议,今天小编专门为大家整理了相关的有效方案,希望对大伙儿有帮助! 移动app开发中多种设备尺寸适配问题,过去只属于And...

法斗斗
2016/01/04
34
0
解决最优子结构问题的两种方法----动态规划和贪心算法

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

thoresa
2015/05/18
0
0
D3.js学习总结(三)——比例尺

在数据可视化的过程中,往往需要将一个值转换为另一个值。例如要绘制一个历年产值的柱状图,我们需要把3000万的产值投射为屏幕上300个像素的高度。以数学上的“函数”为例:y=2x+1。在这里,...

keanu1978
01/22
0
0
(转) 坚持完成这套学习手册,你就可以去 Google 面试了

C++ —— 不使用内建的数据类型。C++ —— 使用内建的数据类型,如使用 STL 的 std::list 来作为链表。Python —— 使用内建的数据类型(为了持续练习 Python),并编写一些测试去保证自己代...

wangxiaocvpr
2016/10/12
0
0
监督学习:KNN(K-近邻)算法实现手写数字识别的三种方法

没人会看的开场白:本来觉得自己从数据建模转人工智能方向应该问题不大(自我感觉自己算法学的不错)。结果一个K-邻近实现手写数字识别的代码就让我改了三四天。虽然网上这方面的代码是很多,...

ufv59to8
05/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

expect脚本同步文件、expect脚本指定host和要同步的文件、构建文件分发系统

expect脚本同步文件 更改权限 执行脚本 查看执行结果 expect eof需要加上,作用是等脚本命令执行完再进行退出 expect脚本指定host和要同步的文件 更改权限,执行脚本 构建文件分发系统 需求背...

Zhouliang6
18分钟前
1
0
Hive应用:外部分区表

Hive应用:外部分区表 介绍 Hive可以创建外部分区表。创建表的时候,分区要在建表语句中体现。建完之后,你不会在表中看到数据,需要进行分区添加,使用alter语句进行添加。然后数据才会显示...

星汉
28分钟前
0
0
点击Enter登录

1. 效果 2. 实现过程(记得引入jq文件) //6.回车事件 登录 $(function() { document.onkeydown = function(event) { var e = event || window.event || arguments.callee.caller.arguments......

Lucky_Me
33分钟前
1
0
点击菜单内容切换

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> <style> .menu{ height: 38px; background-color: #eeeeee; line-height: 38px; } .mao{ ......

南桥北木
今天
1
0
OSChina 周六乱弹 —— 妹子和游戏哪个更好玩

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @andonny :分享唐朝乐队的单曲《国际歌》 《国际歌》- 唐朝乐队 手机党少年们想听歌,请使劲儿戳(这里) @举个栗子- :日常祈雨 邪恶的大祭...

小小编辑
今天
494
6
流利阅读笔记32-20180721待学习

“人工智能”造假:只有人工,没有智能 Lala 2018-07-21 1.今日导读 当今社会,擅长单个方面的人工智能已经盛行,手机借助 AI 智慧防抖技术帮助大家拍出清晰照片,谷歌研发的 AI 助手将可以帮...

aibinxiao
今天
7
0
我的成长记录(一)

今天突然精神抖擞,在我的博客下新开一项分类>成长记录,专门记录每隔一段时间我的一点感悟吧。因为今天才专门花时间新开这样一个分类,所以以前有过的一些感悟没有记录下来,现在已经想不起...

dtqq
今天
1
0
机器学习管理平台 MLFlow

最近工作很忙,博客一直都没有更新。抽时间给大家介绍一下Databrick开源的机器学习管理平台-MLFlow。 谈起Databrick,相信即使是不熟悉机器学习和大数据的工程湿们也都有所了解,它由Spark的...

naughty
今天
12
0
idea tomcat 远程调试

tomcat 配置 编辑文件${tomcat_home}/bin/catalina.sh,在文件开头添加如下代码。    CATALINA_OPTS="-Xdebug -Xrunjdwp:transport=dt_socket,server=y,suspend=n,address=7829" Idea端配......

qwfys
今天
2
0
遍历目录下的文件每250M打包一个文件

#!/usr/bin/env python # -*- utf-8 -*- # @Time : 2018/7/20 0020 下午 10:16 # @Author : 陈元 # @Email : abcmeabc@163.com # @file : tarFile.py import os import tarfile import thr......

寻爱的小草
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部