第十五章 动态规划——钢条切割

前言:动态规划的概念

  动态规划(dynamic programming)是通过组合子问题的解而解决整个问题的。分治算法是指将问题划分为一些独立的子问题,递归的求解各个问题,然后合并子问题的解而得到原问题的解。例如归并排序,快速排序都是采用分治算法思想。本书在第二章介绍归并排序时,详细介绍了分治算法的操作步骤,详细的内容请参考:http://www.cnblogs.com/Anker/archive/2013/01/22/2871042.html。而动态规划与此不同,适用于子问题不是独立的情况,也就是说各个子问题包含有公共的子问题。如在这种情况下,用分治算法则会重复做不必要的工作。采用动态规划算法对每个子问题只求解一次,将其结果存放到一张表中,以供后面的子问题参考,从而避免每次遇到各个子问题时重新计算答案。

动态规划与分治法之间的区别:
(1)分治法是指将问题分成一些独立的子问题,递归的求解各子问题
(2)动态规划适用于这些子问题不是独立的情况,也就是各子问题包含公共子问题

  动态规划通常用于最优化问题(此类问题一般有很多可行解,我们希望从这些解中找出一个具有最优(最大或最小)值的解)。动态规划算法的设计分为以下四个步骤:

(1)描述最优解的结构

(2)递归定义最优解的值

(3)按自低向上的方式计算最优解的值

(4)由计算出的结果构造一个最优解

动态规划最重要的就是要找出最优解的子结构。

一 钢条切割

钢条切割问题描述:给定一段长度为n英寸的钢条和一个价格表Pi(i=1,2,3,...,n),求切割钢铁方案,使得销售收益rn最大。注意,如果长度为n英寸的钢条的价格Pn足够大,最优解可能就是完全不需要切割。

假设一个最优解将钢条切割为k段(对某个1<=k<=n),那么最优切割方案

n=i1+i2+...+ik

将钢条切割的长度分别为i1,i2,...ik的小段,得到的最大收益

rn=pi1+pi2+...+pik

更一般地,对于rn(n>=1),我们可以用更短的最优切割收益来描述它:

rn=max(pn,r1+r(n-1),r2+r(n-2),...,r(n-1)+r1)

第一个参数pn对应不切割,直接出售长度为n英寸的钢条的方案。其他n-1个参数对应另外n-1种方案:对每个i=1,2,...n-1,首先将钢条切割为长度为i和n-i的两端,接着求解这两段的最优切割收益ri和r(n-i)(每种方案的最优收益为两段的最优收益之和)。由于无法预知哪种方案会获得最大收益,我们必须考察所有可能的i,选取其中收益最大者。如果直接出售原钢条会获得最大收益,我们当然可以选择不做任何切割。

自顶向下递归实现

下面是一种直接的自顶向下的递归方法。

CUT-ROD(p,n)

if n==0
    return 0
q=-∞
for i=1 to n
    q=max(q,p[i]+CUT-ROD(p,n-i))
return q

C++实现代码:

#include<iostream>
using namespace std;

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

int main()
{
    int p[11]={0,1,5,8,9,10,17,17,20,24,30};
    int i;
    for(i=0;i<11;i++)
        cout<<cut_rod(p,i+1)<<endl;
}

运行结果:

使用动态规划方法求解最优钢条切割问题

动态规划有两种等价的实现方法,下面以钢条切割问题为例展示这两种方法。

第一种方法称为带备忘的自顶向下法。此方法仍按自然的递归形式编写过程,但过程会保存每个子问题的解(通常保存在一个数组或散列表中)。当需要一个子问题的解时,过程首先检查是否已经保存过此解。如果是,则直接返回保存的值,从而节省了计算时间;否则,按通常方式计算这个子问题。我们称这个递归过程是带备忘的,因为它“记住”了之前已经计算出的结果。

第二种方法称为自底向上法。这种方法一般需要恰当定义子问题“规模”的概念,使得任何子问题的求解都只依赖于“更小的”子问题的求解。因而我们可以将子问题按规模排序,按由小到大的顺序进行求解。当求解某个子问题时,它所依赖的那些更小的子问题都已求解完毕,结果已经保存。每个子问题只需求解一次,当我们求解它(也是第一次遇到它)时,它的所有前提子问题都已经求解完成。

下面给出的是自顶向下CUT-ROD过程的伪代码,加入了备忘机制:

MEMOIZED-CUT-ROD(p,n)
let r[0...n] be a new array
for i=0 to n
    r[i]=-∞

return MEMOIZED-CUT-ROD-AUX(p,n,r)

MEMOIZED-CUT-ROD-AUX(p,n,r)

if r[n]>=0
    return r[i]
if n==0
    q=0
else
    q=-∞
    for i=1 to n
        q=max(q,p[i]+MEMOIZED-CUT-ROD-AUX(p,n-i,r))
r[n]=q
return q

自底向上版本:

BOTTOM-UP-CUT-ROD(p,n)
let r[0..n] be a new array
r[0]=0
for j=1 to n
    q=-∞
    for i=1 to j
        q=max(q,p[i]+r[j-i])
    r[j]=q
return r[n]

 C++代码:

#include<iostream>
using namespace std;

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

//自顶向下
int memoized_cut_rod_aux(int p[],int n,int r[])
{
    int q=-1;
    int i;
    if(r[n]>=0)
        return r[n];
    if(n==0)
        return 0;
    for(i=1;i<=n;i++)
        q=max(q,p[i]+memoized_cut_rod_aux(p,n-i,r));
    r[n]=q;
    return q;
}

int memoized_cut_rod(int p[],int n)
{
    int i;
    int r[n];
    for(i=0;i<=n;i++)
        r[i]=-1;
    return memoized_cut_rod_aux(p,n,r);
}
//自底向上
int cutrod(int p[],int n)
{
    int r[n];
    int i,j;
    for(i=0;i<=n;i++)
        r[i]=0;
    int q;
    for(j=1;j<=n;j++)
    {
        q=-1;
        for(i=1;i<=j;i++)
            q=max(q,p[i]+r[j-i]);
        r[j]=q;
    }
    return r[n];
}
int main()
{
    int p[11]={0,1,5,8,9,10,17,17,20,24,30};
    int i;
    cout<<"递归:"<<endl;
    for(i=0;i<11;i++)
        cout<<cut_rod(p,i)<<endl;
    cout<<"自顶向下:"<<endl;
    for(i=0;i<11;i++)
    {
        cout<<memoized_cut_rod(p,i)<<endl;
    }
    cout<<"自底向上:"<<endl;
     for(i=0;i<11;i++)
    {
        cout<<cutrod(p,i)<<endl;
    }
}

运行结果:

时间: 2024-10-27 00:19:24

第十五章 动态规划——钢条切割的相关文章

第十五章 动态规划——最优二叉搜索树

1.前言: 接着学习动态规划方法,最优二叉查找树问题.二叉查找树参考http://www.cnblogs.com/Anker/archive/2013/01/28/2880581.html.如果在二叉树中查找元素不考虑概率及查找不成功的情况下,可以采用红黑树或者平衡二叉树来搜索,这样可以在O(lgn)时间内完成.而现实生活中,查找的关键字是有一定的概率的,就是说有的关键字可能经常被搜索,而有的很少被搜索,而且搜索的关键字可能不存在,为此需要根据关键字出现的概率构建一个二叉树.比如中文输入法字库中

第十五章 动态规划——矩阵链乘法

前言:今天接着学习动态规划算法,学习如何用动态规划来分析解决矩阵链乘问题.首先回顾一下矩阵乘法运算法,并给出C++语言实现过程.然后采用动态规划算法分析矩阵链乘问题并给出C语言实现过程. 1.矩阵乘法       从定义可以看出:只有当矩阵A的列数与矩阵B的行数相等时A×B才有意义.一个m×r的矩阵A左乘一个r×n的矩阵B,会得到一个m×n的矩阵C.在计算机中,一个矩阵说穿了就是一个二维数组.一个m行r列的矩阵可以乘以一个r行n列的矩阵,得到的结果是一个m行n列的矩阵,其中的第i行第j列位置上的

第十五章 动态规划——最长公共子序列

1.基本概念 一个给定序列的子序列就是该给定序列中去掉零个或者多个元素的序列.形式化来讲就是:给定一个序列X={x1,x2,--,xm},另外一个序列Z={z1.z2.--,zk},如果存在X的一个严格递增小标序列<i1,i2--,ik>,使得对所有j=1,2,--k,有xij = zj,则Z是X的子序列.例如:Z={B,C,D,B}是X={A,B,C,B,D,A,B}的一个子序列,相应的小标为<2,3,5,7>.从定义可以看出子序列直接的元素不一定是相邻的. 公共子序列:给定两个

第十五章 接口[《.net框架程序设计》读书笔记]

.net框架|笔记|程序|设计 第十五章 接口 摘要: 接口的应用及完全限定名方式定义接口的应用. 一. 接口与继承 l C#支持单实现继承和多接口继承 l 接口中可以定义:事件.无参属性(属性).含参属性(索引器):C#不允许接口定义任何静态成员(CLR却允许定义静态成员):CLR不允许接口定义实例字段和构造器. l 缺省为public abstract 方法,但不可用任何修饰符进行修饰(包括public) l 将值类型转换为接口类型(假设其实现了某个接口),则值类型被装箱为引用类型,以调用其

第十五章之(三)RTTI

前言:刚找到新工作,这两天忙着搬家,添加一些日用品,好方便日后使用,浪费了蛮多时间的.所以到现在才补上这一章节. 之前跳过了RTTI,去看下一部分的类型转换运算符,被dynamic_cast搞的很头晕(主要是因为没搞懂为什么用这个),只能回头补上这一节,这时才发现,这一节是不能跳过的. 另外,这小节说实话,蛮难理解的(主要是指其原理,和为什么要有dynamic_cast这个类型转换运算符),这里简单的来概括,就是让指针只有在能安全使用转换后的类方法的情况下,才会被强制转换. ----------

Flash基础理论课 第十五章 3D基础Ⅰ

返回"Flash基础理论课 - 目录" 前面我们做的一切都是二维的(有时只有一维),但是已经可以做出非常酷的东东了.现在,将它们带入到下一个等级. 创建 3D 图形总是那么另人兴奋.新加入的这个维度似乎将物体真正地带入到了生活中.如何在Flash 中实现 3D 在无数的书籍和教学软件中都有介绍.但是我不打算跳过这些内容,我们会很快地将所有基础的知识讲完.随后,将前面章节中讨论的运动效果放到三维空间中.说得详细些,将给大家介绍速度,加速度,摩擦力,反弹,屏幕环绕,缓动,弹性运动,坐标旋转

第十五章-数据访问部件的应用及编程(一)(1)

在这一章里我们主要介绍Delphi的数据访问部件的层次结构.多部件之间的关系.部件的属性.方法.事件以及各部件的应用.这些部件包括: ● TSession部件 ● 数据集部件(TTable和TQuery) ● TDatasource部件 ● 字段对象TField ● 字段编辑器的使用 ● TReport部件和TBatchMove部件 我们对这些部件的属性.方法和事件进行一般性的描述,读者在实际使用Delphi开发应用程序时,还可以通过联机帮助获得有关部件更详细的信息. 15.1 Delphi数据

WF从入门到精通(第十五章):工作流和事务

学习完本章,你将掌握: 1.了解传统的事务模型以及这种模型在哪些地方适合去使用,哪些地方不适合使用 2.懂得在哪些地方不适合传统的事务以及什么时候是补偿事务的恰当时机 3.看看怎样回滚或补偿事务 4.看看怎样修改默认的补偿顺序 如果你是写软件的,你迟早需要去理解事务处理.事务处理(transactional processing)在这个意义上是指写那些把信息记录到一个持久化资源的软件,这些持久化资源如数据库.Microsoft消息队列(它在底层使用了一个数据库).带事务文件系统的Windows

原子变量与非阻塞同步机制(第十五章)

原子变量与非阻塞同步机制 与基于锁的方案相比,非阻塞算法在设计和实现上都要负责得多,但它们在可伸缩性和活跃性上拥有巨大的优势. 原子变量提供了与volatile类型变量相同的内存语义,此外还支持原子的更新操作,从而使它们更加适用于实现计数器.序列发生器和统计数据收集等,同时还能比基于锁的方法提供更高的可伸缩性. 独占锁是一种悲观技术----它假设最坏的情况. 现在,几乎所有的现代处理器中都包含了某种形式的原子读-改-写指令,例如比较并交换(Compare-and-Swap)或者关联加载/条件存储