动态规划例子

篇一：动态规划算法举例分析

动态规划算法

1. 动态规划算法介绍

基本思想是将待求解问题分解成若干子问题，先求解子问题，最后用这些子问题带到原问题，与分治算法的不同是，经分解得到的子问题往往是不是相互独立，若用分治则子问题太多。

2. 适用动态规划算法问题的特征（1）最优子结构

设计动态规划算法的第一步骤通常是要刻画最优解的结构。当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。

在动态规划算法中，问题的最优子结构性质使我们能够以自底向下的方式递归地从子问题的最优解逐步构造出整个问题的最优解。同时，它也使我们能在相对小的子问题空间中考虑问题。

（2）重叠子问题

可用动态规划算法求解的问题应具备的另一基本要素是子问题的重叠性质。在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只有简单地用常数时间查看一下结果。通常，不同的子问题个数随输入问题的大小呈多项式增长。因此，用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。

（3）备忘录方法

动态规划算法的一个变形是备忘录方法。备忘录方法也是一个表格来保存已解决的子问题的答案，在下次需要解此子问题时，只要简单地查看该子问题的解答，而不必重新计算。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。

备忘录方法为每个子问题建立一个记录项，初始化时，该记录项存入一个特殊的值，表示该子问题尚未求解。在求解过程中，对每个待求的子问题，首先查看其相应的记录项。若记录项中存储的是初始化时存入的特殊值，则表示该子问题是第一次遇到，则此时计算出该子问题的解，并保存在其相应的记录项中。若记录项中存储的已不是初始化时存入的特殊值，则表示该子问题已被计算过，其相应的记录项中存储的是该子问题的解答。此时，只要从记录项中取出该子问题的解答即可。

3. 基本步骤

a、找出最优解的性质，并刻画其结构特征。 b、递归地定义最优值。

c、以自底向上的方式计算出最优值。

d、根据计算最优值时得到的信息构造一个最优解。（可省）例1-1 [0/1背包问题] [问题描述]

用贪心算法不能保证求出最优解。在0/1背包问题中，需要对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为值为

，价

。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳

装载是指所装入的物品价值最高，即i?1

xi??0,1??1?i?n?

取得最大值。约束条件为

i?1

xi?c

，

。

在这个表达式中，需要求xi的值。xi=1表示物品i装入背包中，xi=0表示物品i不装入背包。

1.找出最优解性质

考察上述0 / 1背包问题。如前所述，在该问题中需要决定x1，…，xn的值。假设按i = 1，2，…，n 的次序来确定xi 的值。如果置x1 = 0，则问题转变为相对于其余物品（即物品2，3，…，n），背包容量仍为c 的背包问题。若置x1 = 1，问题就变为关于最大背包容量为c-w1 的问题。现设r∈{c，c-w1 } 为剩余的背包容量。

在第一次决策之后，剩下的问题便是考虑背包容量为r 时的决策。不管x1 是0或是1，[x2 ，…，xn ] 必须是第一次决策之后的一个最优方案，如果不是，则会有一个更好的方案[y2，…，yn ]，因而[x1，y2，…，yn ]是一个更好

的方案。因此最优解符合条件，

i?1

xi?

i?2

yi?w1x1?c

。

例：假设n=3, w=[100,14,10], p=[20,18,15], c= 116。若设x1 = 1，则在本次决策之后，可用的背包容量为r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的条件，所得值为1 5，但因为[x2，x3 ]= [1，0] 同样符合容量条件且所得值为1 8，因此[x2，x3 ] = [ 0，1] 并非最优策略。即x= [ 1，0，1] 可改进为x= [ 1，1，0 ]。若设x1 = 0，则对于剩下的两种物品而言，容量限制条件为11 6。总之，如果子问题的结果[x2，x3 ]不是剩余情况下的一个最优解，则[x1，x2，x3 ]也不会是总体的最优解。

2.递归定义最优解

在上述例题的0 / 1背包问题中，最优决策序列由最优决策子序列组成。假设m(i,v) 表示例子中剩余容量为j，剩余物品为i，i+1，…，n 时的最优解的值，即：

?vn

m(n,j)??

j?wn0?j?wn

（1）

和

?max?m(i?1,j),m(i?1,j?wi)?vi??

m(i?1,j)

j?wi0?j?wi

m(i,j)??

（2）

因此，m（1，c）是初始时最优问题的最优解。

现在计算xi值，步骤如下：若m(1 ,c) =m( 2 ,c)，则x1 = 0，否则x1 = 1。接下来需从剩余容量c-w1中寻求最优解，用m(2, c-w1) 表示最优解。依此类推，可得到所有的xi (i= 1，2，…，n) 值。 [0/1背包问题的C语言实现算法]

#define N 12

void Knapsack(int v[],int w[],int c,int n,int m[6][N]) {

int i,j,jMax,k;

jMax=(w[n]-1<c?w[n]-1:c); for(i=0;i<=jMax;i++) m[n][i]=0;

for(i=w[n];i<=c;i++) m[n][i]=v[n];

for(i=n-1;i>1;i--)

{

jMax=(w[i]-1<c?w[i]-1:c);for(j=0;j<=jMax;j++)m[i][j]=m[i+1][j];for(j=w[i];j<=c;j++)

{

k=j-w[i];

if(m[i+1][j]<m[i+1][k]+v[i]) m[i][j]=m[i+1][k]+v[i]; else

m[i][j]=m[i+1][j];} }

m[1][c]=m[2][c]; if(c>=w[1]) {

k=c-w[1];

m[1][c]=(m[2][c]>m[2][k]+v[1])?m[2][c]:m[2][k]+v[1]; } }

void Traceback(int m[6][N],int w[],int c,int n,int x[]) {

int i;

for(i=1;i<N;i++) {

if(m[i][c]==m[i+1][c]) x[i]=0;else{ x[i]=1; c-=w[i];} }

x[n]=(m[n][c])?1:0; }

main()

{

int i,c=10,n=5,w[]={0,2,2,6,5,4},v[]={0,6,3,5,4,6};int m[6][N]={0};int x[6]={0};int j;

Knapsack(v,

动态规划例子

w,c,n,m);for(i=1;i<=n;i++){

for(j=1;j<=c;j++)

printf("%3d",m[i][j]); printf("\n"); }

Traceback(m,w,c,n,x); for(i=1;i<=n;i++) {

if(x[i])

printf("%4d:%4d",i,v[i]); }

printf("\n"); }

例2-1 [最短路径问题] [问题描述]

篇二：动态规划的很经典的教程

动态规划的很经典的教程

引言：本人在做过一些题目后对DP有些感想，就写了这个总结：

第一节动态规划基本概念

一，动态规划三要素：阶段，状态，决策。

他们的概念到处都是，我就不多说了，我只说说我对他们的理解：

如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的不同的环节，状态就是工件当前的形态，决策就是对工件的操作。显然不同阶段是对产品的一个前面各个状态的小结，有一个个的小结构成了最终的整个生产线。每个状态间又有关联（下一个状态是由上一个状态做了某个决策后产生的）。

下面举个例子：

要生产一批雪糕，在这个过程中要分好多环节：购买牛奶，对牛奶提纯处理，放入工厂加工，加工后的商品要包装，包装后就去销售……，这样每个环节就可以看做是一个阶段；产品在不同的时候有不同的状态，刚开始时只是白白的牛奶，进入生产后做成了各种造型，从冷冻库拿出来后就变成雪糕（由液态变成固态=_=||）。每个形态就是一个状态，那从液态变成固态经过了冰冻这一操作，这个操作就是一个决策。

一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。

经过这个例子相信大家对动态规划有所了解了吧。下面在说说我对动态规划的另外一个理解：

用图论知识理解动态规划：把动态规划中的状态抽象成一个点，在有直接关联的状态间连一条有向边，状态转移的代价就是边上的权。这样就形成了一个有向无环图AOE网（为什么无环呢？往下看）。对这个图进行拓扑排序，删除一个边后同时出现入度为0的状态在同一阶段。这样对图求最优路径就是动态规划问题的求解。

二，动态规划的适用范围

动态规划用于解决多阶段决策最优化问题，但是不是所有的最优化问题都可以用动态规划解答呢？一般在题目中出现求最优解的问题就要考虑动态规划了，但是否可以用还要满足两个条件：最优子结构（最优化原理）无后效性

最优化原理在下面的最短路径问题中有详细的解答；什么是无后效性呢？

就是说在状态i求解时用到状态j而状态j就解有用到状态k…..状态N。

而求状态N时有用到了状态i这样求解状态的过程形成了环就没法用动态规划解答了，这也是上面用图论理解动态规划中形成的图无环的原因。

也就是说当前状态是前面状态的完美总结，现在与过去无关。。。

当然，有时换一个划分状态或阶段的方法就满足无后效性了，这样的问题仍然可以用动态规划解。

三，动态规划解决问题的一般思路。

拿到多阶段决策最优化问题后，第一步要判断这个问题是否可以用动态规划解决，如果不能就要考虑搜索或贪心了。当确定问题可以用动态规划后，就要用下面介绍的方法解决问题了：

（1）模型匹配法：

最先考虑的就是这个方法了。挖掘问题的本质，如果发现问题是自己熟悉的某个基本的模型，就直接套用，但要小心其中的一些小的变动，现在考题一般都是基本模型的变形套用时要小心条件，三思而后行。这

些基本模型在先面的分类中将一一介绍。

（2）三要素法

仔细分析问题尝试着确定动态规划的三要素，不同问题的确定方向不同： a.先确定阶段的问题：数塔问题，和走路问题（详见解题报告） b.先确定状态的问题：大多数都是先确定状态的。 c.先确定决策的问题：背包问题。（详见解题报告）

一般都是先从比较明显的地方入手，至于怎么知道哪个明显就是经验问题了，多做题就会发现。（3）寻找规律法：

这个方法很简单，耐心推几组数据后，看他们的规律，总结规律间的共性，有点贪心的意思。（4）边界条件法

找到问题的边界条件，然后考虑边界条件与它的领接状态之间的关系。这个方法也很起效。（5）放宽约束和增加约束

这个思想是在陈启锋的论文里看到的，具体内容就是给问题增加一些条件或删除一些条件使问题变的清晰。

第二节动态规划分类讨论

这里用状态维数对动态规划进行了分类：

1.状态是一维的

1．1下降/非降子序列问题：

问题描述： {挖掘题目的本质，一但抽象成这样的描述就可以用这个方法解}

在一个无序的序列a1,a2,a3,a4…an里，找到一个最长的序列满足：ai<=aj<=ak…<=am,且i<j<k…<m.（最长非降子序列）或ai>aj>ak…>am,且i>j>k…>m.（最长下降子序列）。

问题分析：

如果前i-1个数中用到ak (ak>ai或ak<=ai)构成了一个的最长的序列加上第I个数ai就是前i个数中用到i的最长的序列了。那么求用到ak构成的最长的序列有要求前k-1个数中……

从上面的分析可以看出这样划分问题满足最优子结构，那满足无后效性么？显然对于第i个数时只考虑前i-1个数,显然满足无后效性，可以用动态规划解。

分析到这里动态规划的三要素就不难得出了：如果按照序列编号划分阶段，设计一个状态opt[i] 表示前i个数中用到第i个数所构成的最优解。那么决策就是在前i-1个状态中找到最大的opt[j]使得aj>ai(或aj<=ai)，opt[j]+1就是opt[i]的值；用方程表示为：{我习惯了这种写法，但不是状态转移方程的标准写法 }

opt[i]=max(opt[j])+1(0<=j<i 且aj<=ai) {最长非降子序列} opt[i]=max(opt[j])+1(0<=j<i 且aj>ai) {最长下降子序列} 实现求解的部分代码：

opt[0]:=maxsize；{maxsize 为maxlongint或-maxlongint} for i:=1 to n do for j:=0 to i-1 do

if ( a[j]>a[i]) and (opt[j]+1>opt[i]) then opt[i]:=opt[j]+1; ans:=-maxlongint; for i:=1 to n do

if opt[i]>ans then ans:=opt[i]; {ans 为最终解}

复杂度：从上面的实现不难看出时间复杂度为O（N2），空间复杂度O（N）；

(missile.pas/c/cpp) 来源：NOIP1999(提高组) 第一题【问题描述】

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

【输入文件】missile.in

单独一行列出导弹依次飞来的高度。【输出文件】missile.out

两行，分别是最多能拦截的导弹数，要拦截所有导弹最少要配备的系统数【输入样例】

389 207 155 300 299 170 158 65 【输出样例】 6 2

【问题分析】

有经验的选手不难看出这是一个求最长非升子序列问题，显然标准算法是动态规划。

以导弹依次飞来的顺序为阶段，设计状态opt[i]表示前i个导弹中拦截了导弹i可以拦截最多能拦截到的导弹的个数。

状态转移方程：

opt[i]=max(opt[j])+1 (h[i]>=h[j],0=<j<i){h[i]存，第i个导弹的高度} 最大的opt[i]就是最终的解。

这只解决了第一问，对于第二问最直观的方法就是求完一次opt[i]后把刚才要打的导弹去掉，在求一次opt[i]直到打完所有的导弹，但这样做就错了。

不难举出反例： 6 1 7 3 2 错解： 6 3 2/1/7正解：6 1/7 3 2

其实认真分析一下题就回发现：每一个导弹最终的结果都是要被打的，如果它后面有一个比它高的导弹，那打它的这个装臵无论如何也不能打那个导弹了，经过这么一分析，这个问题便抽象成在已知序列里找最长上升序列的问题。

求最长上升序列和上面说的求最长非升序列是一样的，这里就不多说了。复杂度：时间复杂度为O（N2），空间复杂度为O（N）。【源代码】 program missile; const

fin='missile.in'; fout='missile.out'; maxn=10000;

var

a,opt:array[0..maxn] longint;

n,anslen,anstime:longint; procedure init;

var x:longint; begin

assign(input,fin); reset(input);

assign(output,fout); rewrite(output); n:=0; repeat inc(n); read(a[n]); until seekeof; end;

procedure main; var i,j:longint; begin

fillchar(opt,sizeof(opt),0); a[0]:=maxlongint; for i:=1 to n do for j:=i-1 downto 0 do

if (a[j]>=a[i]) and if opt[i]>anstime then anstime:=opt[i]; end;

procedure print; begin

writeln(anslen); writeln(anstime); close(input); close(output); end; begin

(opt[j]+1>opt[i]) then

opt[i]:=opt[j]+1; anslen:=0; for i:=1 to n do if opt[i]>anslen then anslen:=opt[i];

fillchar(opt,sizeof(opt),0); a[0]:=-maxlongint; for i:=1 to n do for j:=i-1 downto 0 do if

(a[j]<a[i])

and

(opt[j]+1>opt[i]) then

opt[i]:=opt[j]+1; anstime:=0; for i:=1 to n do

init; main; print; end.

(chorus.pas/c/cpp) 来源：NOIP2004(提高组) 第一题

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

【输入文件】

输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

【输出文件】

输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。【样例输入】 8

186 186 150 200 160 130 197 220 【样例输出】 4

【数据规模】

对于50％的数据，保证有n<=20；对于全部的数据，保证有n<=100。【问题分析】

出列人数最少，也就是说留的人最多，也就是序列最长。

这样分析就是典型的最长下降子序列问题。只要枚举每一个人站中间时可以的到的最优解。显然它就等于，包括他在内向左求最长上升子序列，向右求最长下降子序列。

我们看一下复杂度：

计算最长下降子序列的复杂度是O（N2），一共求N次，总复杂度是O（N3）。这样的复杂度对于这个题的数据范围来说是可以AC的。但有没有更好的方法呢？

其实最长子序列只要一次就可以了。因为最长下降（上升）子序列不受中间人的影响。

只要用OPT1求一次最长上升子序列，OPT2求一次最长下降子序列。这样答案就是N-max(opt1[i]+opt2[i]-1).

复杂度由O（N3）降到了O（N2）。【源代码】 program chorus; const fin='chorus.in'; fout='chorus.out'; maxn=200; var

opt1,opt2,a:array[0..maxn] of longint;

n,ans:longint; procedure init; var i:longint; begin

assign(input,fin); reset(input); assign(output,fout); rewrite(output);

(buylow.pas/c/cpp) 来源: USACO 4-3-1 【问题描述】

?逢低吸纳?是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀: "逢低吸纳,越低越买"

这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。

给定连续的N天中每天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。写一个程序，求出最多能买几次股票。

以下面这个表为例, 某几天的股价是: 天数 1 2 3 4 5 6 7 8 9 10 11 12 股价 68 69 54 64 68 64 70 67 78 62 98 87

这个例子中, 聪明的投资者(按上面的定义)，如果每次买股票时的股价都比上一次买时低，那么他最多能买4次股票。一种买法如下(可能有其他的买法):

天数 2 5 6 10

readln(n); for i:=1 to n do read(a[i]); end;

procedure main; var i,j:longint; begin

a[0]:=-maxlongint; for i:=1 to n do for j:=i-1 downto 0 do if

(a[j]<a[i])

and

(opt1[j]+1>opt1[i]) then

opt1[i]:=opt1[j]+1; a[n+1]:=-maxlongint; for i:=n downto 1 do for j:=i+1 to n+1 do if

(a[j]<a[i])

and

(opt2[j]+1>opt2[i]) then

opt2[i]:=opt2[j]+1; ans:=0; for i:=1 to n do

if opt1[i]+opt2[i]>ans then ans:=opt1[i]+opt2[i]; end;

procedure print; begin

writeln(n-ans+1); close(input); close(output); end; begin init; main; print; end.

篇三：动态规划matlab仿真实例

动态规划在火力分配中的应用。 1. 问题描述

设有m个目标，目标价值（重要性和危害性）各不相同，用数值AK（K=1，2，..m）表示，计划用n枚导弹突袭，导弹击毁目标的概率PK=1????????????，其中????是常数，取决于导弹的特性与目标的性质；????为向目标发射的导弹数，问题：做出方案使预期的突击效果最大。

2. 问题建模

上述问题可以表述为

max??= ????(1????????????)

??=1

约束条件为

????=1????=??（????为非负整数）

3. 算法描述

下面通过一个实例说明：设目标数目为4（m=4），导弹为5（n=5），????和aK取值情况如下表所示：表1：Ak，????取值情况

将火力分配可分为4个阶段，每个阶段指标函数为：

??1 ??1 =8(1????0.2??1)??2 ??2 =7(1????0.3??2) ??3 ??3 =6(1????0.5??3)??4 ??4 =3(1????0.9??4)

????可能取值为0，1，2，3，4，5，将函数值带人如下表：

表2函数值

动态规划问题基本方程为：

???? ???? =max?{???? ???? +????+1 ????????? }c ??5 ??5 =0 逐次向前推一级

K=4 ??4 ??4 =??4 ??4 =3(1????0.9??4) K=3??3 ??3 =max?{??3 ??3 +??4 ??3???3 }=

max?{6(1????0.5??3)+ ??4 ??3???3 }

K=2 ??2 ??2 =max?{??2 ??2 +??3 ??2???2 }= max?{7(1????0.3??2)+ ??3 ??2???2 }

K=1 ??1 ??1 = max?{??1 ??1 +??2 ??1???1 }= max?{8(1????0.2??1)+ ??2 ??1???1 }（0<????<5可取等号）

只需要求解??1 5 的最大值然后反推回去就可以获得最优的分配方案

4. Matlab仿真求解

因为????与????取值为整数，可以采用动态规划的方法，获得??1 5 的最大值，对应的最优方案

function[p_opt,fval]=dynprog(x,DecisFun,SubObjFun,TransFun,ObjFun) %求解动态规划问题最小值函数

k=length(x(1,:)) %判断决策级数

x_isnan=~isnan(x); % 非空状态矩阵

t_vubm=inf*ones(size(x)); % 性能指标中间矩阵 f_opt=nan*ones(size(x)); % 总性能指标矩阵 d_opt=f_opt; %每步决策矩阵

tmp1=find(x_isnan(:,k)); % 最后一步状态向量 tmp2=length(tmp1); % 最后一步状态个数 fori=1:tmp2

u=feval(DecisFun,k,x(tmp1(i),k)); tmp3=length(u);%决策变量

for j=1:tmp3 % 求出当前状态下所有决策的最小性能指标 tmp=feval(SubObjFun,k,x(tmp1(i),k),u(j)); iftmp<= t_vubm(i,k) %t_vub f_opt(i,k)=tmp; d_opt(i,k)=u(j); t_vubm(i,k)=tmp; end; end; end

for ii=k-1:-1:1

tmp10=find(x_isnan(:,ii)); tmp20=length(tmp10);

for i=1:tmp20 %求出当前状态下所有可能的决策u=feval(DecisFun,ii,x(tmp10(i),ii));tmp30=length(u) ;

for j=1:tmp30 % 求出当前状态下所有决策的最小性能指标

tmp00=feval(SubObjFun,ii,x(tmp10(i),ii),u(j)); % 单步性能指标 tmp40=feval(TransFun,ii,x(tmp10(i),ii),u(j)); % 下一状态 tmp50=x(:,ii+1)-tmp40; % 找出下一状态在 x 矩阵的位置 tmp60=find(tmp50==0) ; if~isempty(tmp60)

if nargin<6 %矩阵不同需要修改nargin的值，很重要

tmp00=tmp00+f_opt(tmp60(1),ii+1); % set the default object value else

tmp00=feval(ObjFun,tmp00,f_opt(tmp60(1),ii+1)); end %当前状态的性能指标 if tmp00<=t_vubm(i,ii)f_opt(i,ii)=tmp00; d_opt(i,ii)=u(j); t_vubm(i,ii)=tmp00; end; end; end;

end

fval=f_opt(:,1);

tmp0 = find(~isnan(fval)); fval=fval(tmp0,1);

p_opt=[];tmpx=[];tmpd=[];tmpf=[]; tmp01=length(tmp0); fori=1:tmp01

tmpd(i)=d_opt(tmp0(i),1); tmpx(i)=x(tmp0(i),1);

tmpf(i)=feval(SubObjFun,1,tmpx(i),tmpd(i));

p_opt(k*(i-1)+1,[1,2,3,4])=[1,tmpx(i),tmpd(i),tmpf(i)]; for ii=2:k

tmpx(i)=feval(TransFun,ii,tmpx(i),tmpd(i));tmp1=x(:,ii)-tmpx(i);tmp2=find(tmp1==0); if ~isempty(tmp2)

tmpd(i)=d_opt(tmp2(1),ii); end

tmpf(i)=feval(SubObjFun,ii,tmpx(i),tmpd(i));

p_opt(k*(i-1)+ii,[1,2,3,4])=[ii,tmpx(i),tmpd(i),tmpf(i)]; end; end;

下面编写四个函数：

function u = DecisF1( k,x ) %决策函数 if k==4 u=x; else u=0:x; end

function y = TransF1( k,x,u )%状态转移方程 y=x-u;

function v = SubObjF1( k,x,u )%阶段k的指标函数 a=[0.2,0.3,0.5,0.9]; A=[8,7,6,3];

v=A(k)*(1-exp(-a(k)*u)); v=-v;%max变为min

function y = ObjF1( v,f )%基本方程中的函数 y=v+f;

y=-y;%max变为min

测试代码：

n=5;

x1=[n;nan*ones(n,1)];

x2=0:n;x2=x2';x=[x1,x2,x2,x2];

[p,f]=dynprog(x,'DecisF1','SubObjF1','TransF1','ObjF1') %p为分配方案，f为结果

5. Matlab仿真结果分析

运行结果显示： P为方案：

即对目标1发射1枚导弹，对目标2发射1枚，对目标3发射2枚，对目标4发生1枚导弹，能获得最大效能。

f为最大的效能：

即在这种分配下的最大效能为

8.8374