C++语言：13.6.1动态规划

动态规划算法通常用于求解具有最优性质的问题。

1.基本概念

动态规划是运筹学中用于求解决策过程中的最优化数学方法。当然，本书关注的是作为一种算法设计技术，作为一种使用多阶段决策过程最优的通用方法。

动态规划过程是:每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就被称为动态规划。

2.基本思想与策略

动态规划的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题(阶段)，按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。动态规则与分治法最大的差别是:适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上的进一步的求解)。

3.适用的情况

能采用动态规划求解的问题的一般具有以下3个性质。

(1)最优化原理:假设问题的最优解所包括的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

(2)无后效性:即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响曾经的状态，仅仅与当前状态有关。

(3)有重叠子问题:即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到(该性质并非动态规划适用的必要条件，可是假如没有这条性质，动态规划算法同其他算法相比就不具备优势)。动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。

4.动态规划的具体步骤

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线):

初始状态→│决策1│→│决策2│→…→│决策n│→结束状态

动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

(1)划分阶段:按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

(2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

(3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

(4)寻找边界条件:给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程(包括边界条件)。

在实际应用中，可以按以下几个简化的步骤进行设计:

(1)分析最优解的性质，并刻画其结构特征。

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

(3)以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值。(www.xing528.com)

(4)根据计算优值时得到的信息，构造问题的最优解。

例13－8　走台阶问题。

有n级台阶，一个人每次上一级或者两级，请问有多少种走完n级台阶的方法?为了防止溢出，请将结果Mod 1000000007。

给定一个正整数n，请返回一个数，代表上楼的方式数。保证n小于等于100 000。

解析:这是一个非常经典的问题，设f(n)为上n级台阶的方法，要上到n级台阶的最后一步有两种方式:从n－1级台阶走一步；从n－2级台阶走两步，于是就有了这个公式:f(n)＝f(n－1)＋f(n－2)。

代码如下:

一、选择题

1.给定原始数据序列是有序的，对该序列进行排序，采用下列哪种排序方法最好?(　)。

A.快速排序 B.插入排序 C.选择排序 D.冒泡排序

2.给定长度为n的数据序列，采用冒泡法进行排序，则比较的次数为(　)。

A.n B.n2 C.2n D.n(n－1)2/2

3.给定长度为n的数据序列，采用插入排序法进行排序，则比较的次数最多为(　)。

A.n B.n(n－1)/2 C.2n D.n(n－1)

二、编程题

1.给定长度为n(n<＝500)的数据序列，将其排成从小到大的数据序列，并输出每个数据的原始输入顺序。例如:

输入:

输出:

2.找出1～3 000中能被17整除的数据并输出显示。

3.编辑一个程序对于给定的一个自然数n，找出满足关系式s＝qn＋pn，且q、p、s是自然数并都小于1 000的s值。

4.在n×n的国际象棋上的某一位置上放置一个马，然后采用象棋中“马走日字”的规划，要求马走过棋盘中的每一个格且不能重复，用回溯方法解决。

5.用迭代方法求的值，x由键盘输入，初始值是y0＝x，迭代公式是，要求误差小于10－6。

6.某班级为了表彰在运动会上的优秀者，班委会决定利用剩余的班费来购买奖品。奖品的价钱分为6元、5元、4元三种，为使购买奖品数量符合实际情况，请设计程序给出可参考的购买方案。