用动态规划求解非线性规划问题：

设 MAX Z=x1(x2^2)x3

st{ x1+x22+x3<=8

x1,x2,x3>=0

将该问题分为三个阶段，令S0,S1,S2,S3分别表示状态变量，且S3<=8,取x1,x2,x3为各阶段决策变量，最优值函数Fk(Sk)表示第k阶段结束状态为Sk时从第1至第k阶段的最大值，故

x1=s1,2x2+S1=S2,x3+S2=S3<=8

所以 x1=S1,0=<x2<=S2/2,0=<x3<=S3

且 S1=S2-2x2,S2=S3-x3

用逆序递推法可知：

F1(S1)=max(x1)[其中 x1=s1]

则 (x1) =S1 , F1(S1)=S1

F2(S2)=max(x2^2F1(S1))

=max[x2^2(S2-2x2)]

(其中 0=<x2<=S2/2)

则 (x2) =S2/3 , F2(S2)=(S2^3)/27

F3(S3)=max(x3F2(S2))

=max[x3(S2^3)/27]

(其中 0=<x3<=S3)

则 (x3) =S3/4 , F3(S3)=(S3^4)/256

经分析可知，当S3=8时，F3(S3)=(S3^2)/4=16

此时达最大。故反推得：

(x3) =S3/4=2 ，S2=S3-x3=8-2=6

(x2) =S2/3=2 ，S1=S2-2x2=6-4=2

(x1) =S1=2

MAX Z=x1(x2^2)x3=16

题目 名称 算法

1997-c1 数矩形 数学（乘法原理）

1997-c2 数字三角形 穷举

1997-c3 数路径 递推（迭代）+加法原理+高精度

1997-g1 素数方阵 递归回溯+构造

1997-g2 表达式判错 字符串+栈

1997-g3 骑士游历 宽搜+递推

1998-c1 1:2:3 穷举

1998-c2 S! 高精度

1998-c3 2的幂次方 递归+二进制

1998-g1 上下车问题 递推或者枚举

1998-g2 连接多位数 贪心+字符串

1998-g3 加法表 递归+直接判断

1999-c1 Cantor表 数学

1999-c2/g2 回文数 字符串

1999-c3/g3 旅行家的预算 贪心

1999-g1 导d拦截 动态规划、贪心

1999-g4 邮票面值设计 搜索+优化

2000-c1 计算器的改良 字符串

2000-c2 税收与补贴问题 数学或穷举

2000-c3/g2 乘积最大 动态规划+高精度

2000-c4/g3 单词接龙 回溯

2000-g1 进制转换 类比+穷举

2000-g4 方格取数 动态规划

2001-c1 数的计数 递归或递推或动态规划

2001-c2 最大公约数与最小公倍数 穷举+优化+乘法原理

2001-c3 二叉树的先序序列 递归或穷举，构造

2001-c4 装箱问题 宽搜+hash表，或动态规划

2001-g1 一元三次方程求解 穷举或随机化+迭代

2001-g2 数的划分 递推或动态规划

2001-g3 统计单词个数 贪心或随机化或动态规划

2001-g4 Car的旅行路线 图论（Dijkstra算法）

2002-c1 级数求和 高精度

2002-c2 选数 搜索（递归）

2002-c3 产生数 乘法原理+图论

2002-c4 过河卒 递推+加法原理+高精度

2002-g1 均分纸牌 数学

2002-g2 字串变换 广搜（双向）+剪枝

2002-g3 自由落体 物理题

2002-g4 矩形覆盖 搜索（全国没有1人对）

归纳：递推、动态规划、贪心、搜索、数学（物理）、图论、高精度、回溯、穷举、字符串

NOIP2004~2008提高组复赛算法及难度分析

竞赛 试题名称 算法 构造难度 实现难度 综合难度

NOIP2004 津津的储蓄计划 模拟 1 1 1

合并果子 排序+二分查找 2 2 2

合唱队形 动态规划 4 2 3

虫食算 搜索 3 5 4

NOIP2005 谁拿了最多奖学金 模拟 1 1 1

过河 数学或动态规划 4 3 3

篝火晚会 图论或数学 4 2 3

等价表达式 分治 4 5 5

NOIP2006 能量项链 动态规划 3 1 2

金明的预算方案 动态规划 4 3 4

作业调度方案 模拟 2 4 3

2^k进制数 数学+高精 2 4 3

NOIP2007 统计数字 排序 2 1 1

字符串的展开 模拟 2 5 4

矩阵取数游戏 动态规划+高精 4 4 4

树网的核 图论 5 4 4

NOIP2008 笨小猴 模拟 1 1 1

火柴棒等式 搜索或数学 1 3 2

传纸条 动态规划 3 2 3

双栈排序 图论 5 4 5

0） 穷举法

穷举法简单粗暴，没有什么问题是搞不定的，只要你肯花时间。同时对于小数据量，穷举法就是最优秀的算法。就像太祖长拳，简单，人人都能会，能解决问题，但是与真正的高手过招，就颓了。

1） 贪婪算法

贪婪算法可以获取到问题的局部最优解，不一定能获取到全局最优解，同时获取最优解的好坏要看贪婪策略的选择。特点就是简单，能获取到局部最优解。就像打狗棍法，同一套棍法，洪七公和鲁有脚的水平就差太多了，因此同样是贪婪算法，不同的贪婪策略会导致得到差异非常大的结果。

2） 动态规划算法

当最优化问题具有重复子问题和最优子结构的时候，就是动态规划出场的时候了。动态规划算法的核心就是提供了一个memory来缓存重复子问题的结果，避免了递归的过程中的大量的重复计算。动态规划算法的难点在于怎么将问题转化为能够利用动态规划算法来解决。当重复子问题的数目比较小时，动态规划的效果也会很差。如果问题存在大量的重复子问题的话，那么动态规划对于效率的提高是非常恐怖的。就像斗转星移武功，对手强它也会比较强，对手若，他也会比较弱。

3）分治算法

分治算法的逻辑更简单了，就是一个词，分而治之。分治算法就是把一个大的问题分为若干个子问题，然后在子问题继续向下分，一直到base cases，通过base cases的解决，一步步向上，最终解决最初的大问题。分治算法是递归的典型应用。

4） 回溯算法

回溯算法是深度优先策略的典型应用，回溯算法就是沿着一条路向下走，如果此路不同了，则回溯到上一个

分岔路，在选一条路走，一直这样递归下去，直到遍历万所有的路径。八皇后问题是回溯算法的一个经典问题，还有一个经典的应用场景就是迷宫问题。

5） 分支限界算法

回溯算法是深度优先，那么分支限界法就是广度优先的一个经典的例子。回溯法一般来说是遍历整个解空间，获取问题的所有解，而分支限界法则是获取一个解（一般来说要获取最优解）。

动态规划算法 概念及意义动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家REBellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。 基本模型

多阶段决策过程的最优化问题。

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图）

这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。 记忆化搜索 给你一个数字三角形, 形式如下:

1

2 3

4 5 6

7 8 9 10

找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大

无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)}

对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。

解决方法：

我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的递归过程 :

f1:=f(i-1,j+1); f2:=f(i-1,j);

if f1>f2 then f:=f1+a[i,j] else f:=f2+a[i,j];

显而易见，这个算法就是最简单的搜索算法。时间复杂度为2^n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个opt数组：Opt[i, j] - 每产生一个f(i, j)，将f(i, j)的值放入opt中，以后再次调用到f(i, j)的时候，直接从opt[i, j]来取就可以了。于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，避免了动态规划状态转移先后的问题，而且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的 状态 决策

决策：

当前状态通过决策,回到了以前状态可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。

状态：

我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。我们就从动态规划的要诀，也就是核心部分“状态”开始，来逐步了解动态规划。有时候当前状态确定后,以前状态就已经确定,则无需枚举

动态规划算法的应用 一、动态规划的概念

近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。

要了解动态规划的概念，首先要知道什么是多阶段决策问题。

1 多阶段决策问题

如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。

各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果

2．动态规划问题中的术语

阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。

在前面的例子中，第一个阶段就是点A，而第二个阶段就是点A到点B，第三个阶段是点B到点C，而第四个阶段是点C到点D。

状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。

在前面的例子中，第一个阶段有一个状态即A，而第二个阶段有两个状态B1和B2，第三个阶段是三个状态C1，C2和C3，而第四个阶段又是一个状态D。

过程的状态通常可以用一个或一组数来描述，称为状态变量。一般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的处理将会有很大的好处。此外，状态可以有多个分量(多维情形)，因而用向量来代表；而且在每个阶段的状态维数可以不同。

当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。

无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。

决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多间题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。

决策变量的范围称为允许决策集合。

策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。

给定k阶段状态变量x(k)的值后，如果这一阶段的决策变量一经确定，第k+1阶段的状态变量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化，那么可以把这一关系看成(x(k)，u(k))与x(k+1)确定的对应关系，用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律，称为状态转移方程。

最优性原理:作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。

最优性原理实际上是要求问题的最优策略的子策略也是最优。让我们通过对前面的例子再分析来具体说明这一点：从A到D，我们知道，最短路径是A�8�1B1�8�1C2�8�1D，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优：A�8�1B1�8�1C2是A到C2的最短路径，B1�8�1C2�8�1D也是B1到D的最短路径……──事实正是如此，因此我们认为这个例子满足最优性原理的要求。

以上就是关于用动态规划求解非线性规划问题：全部的内容，包括:用动态规划求解非线性规划问题：、关于noip的问题、c语言常用算法有哪些等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！