动态规划法及其应用示例

《动态规划法及其应用示例》由会员分享，可在线阅读，更多相关《动态规划法及其应用示例（9页珍藏版）》请在装配图网上搜索。

1、动态规划求0/1背包问题#include#include#include/goods是一个或多个物品的重量和价值typedef struct goodsint weight;int value; goods;/用来定义一个queryList数组/数组中的每个元素定义一趟需要记录的数据typedef struct queryListgoods *subResult; /一趟需要记录的数据int end; /指示该趟数据的最后一个元素 queryList;queryList* dknap(goods *Goods, int count, int capacity)int i, j, next, p

2、re, index, k;queryList *ql;goods cur;ql = (queryList *)malloc(sizeof(queryList)*count);ql0.subResult = (goods*)malloc(sizeof(goods);ql0.end = 0;ql0.subResult-weight = 0;ql0.subResult-value = 0;for(i=1;iqli-1.subResultpre.weight)if (cur.value = qli-1.subResultpre.value) /抛弃旧元素pre+;else /插入新生成元素qli.su

3、bResultindex.weight = cur.weight;qli.subResultindex.value = cur.value;index+;cur.weight = qli-1.subResultnext.weight + Goodsi-1.weight;cur.value = qli-1.subResultnext.value + Goodsi-1.value; next+;elseif (cur.value = qli-1.subResultpre.value) /抛弃旧兀素pre+;else 抛弃新生成元素cur.weight = qli-1.subResultnext.w

4、eight + Goodsi-1.weight;cur.value = qli-1.subResultnext.value + Goodsi-1.value;next+;/插入剩余的新生成元素for(j=next-1;j capacity)break;qli.subResultindex.weight = qli-1.subResultj.weight + Goodsi-1.weight;qli.subResultindex.value = qli-1.subResultj.value + Goodsi-1.value; index+;qli.end=index-1;printf(i=%dn”

5、, i);for(j=0;j=0;i-)k=qli.end;while (k=0)if (qli.subResultk.weightcapacity) k-;else break;j=k;while (j=0)if (qli.subResultj.weight+Goodsi.weightcapacity)j-;else break;if (k=0 j=qli.subResultj.value+Goodsi.value) printf(a%d=%dn, i, 0);elseprintf(a%d=%dn, i, 1);capacity = capacity - Goodsi.weight;int

6、main()goods Goods = 2,1, 3, 2, 4, 5;dknap(Goods, sizeof(Goods)/sizeof(Goods0), 6);/goods Goods = 100, 100, 50, 50, 20, 20, 10, 10, 7, 7, 3, 3;/dknap(Goods, sizeof(Goods)/sizeof(Goods0), 165);最长公共子串问题的实现最长公共子串问题：一个给定序列的子序列是在该序列中删去若干元素后得到的序列。 给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X 和Y的公共子序列。最长公共子串就是求给定

7、两个序列的一个最长公共子序列。例如， X=“ABCBDAB”，Y=“BCDB”是 X 的一个子序列。问题分析：给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。 问题要求已知两序列A和B的最长公共子序列。如采用列举A的所有子序列，并一一检查 其是否又是B的子序列，并随时记录所发现的子序列，最终求出最长公共子序列。这种方 法因耗时太多而不可取。考虑最长公共子序列问题如何分解成子问题，设A=a0，a1，am-1”，B=b0，b1， bm-1”，并Z=z0，z1，zk-1”为它们的最长公共子序列。不难证明有以下性质：（1） 如果 am-1=bn-1，则 zk-1=am-1=

8、bn-1，且“z0，z1，zk-2”是“a0，a1，am-2” 和“b0，b1，bn-2”的一个最长公共子序列；（2） 如果 am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，zk-1”是“a0，a1，am-2” 和“b0，b1，bn-1”的一个最长公共子序列；（3） 如果 am-1!=bn-1，则若zk-1!=bn-1，蕴涵z0，z1，zk-1”是“a0，a1，am-1” 和“b0，b1，bn-2”的一个最长公共子序列。这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0， a1，am-2”和“b0，b1，bm-2”的一个 最长公共子序列；

9、如果am-1!=bn-1，则要解决 两个子问题，找出“a0, al,，am-2”和“b0, bl,，bn-1”的一个最长公共子序列 和找出 “a0, al，am-1”和，“b0，bl，bn-2”的一个最长公共子序列，再取两者中较长者作为 A和B的最长公共子序列。为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所 有子问题的解存于该数组中，这就是动态规划法所采用的基本方法，具体说明如下。定义cij为序列a0, al,，ai-2”和“b0, bl,，bj-1”的最长公共子序列的长度，计 算cij可递归地表述如下：(1) cij = 0如果 i=0 或 j=0；(2) ci

10、j = ci-lj-l+l 如果 i,j0，且 ai-l = bj-l；(3) cij = maxcij-l, ci-lj如果 i,j0，且 ai-l != bj-l。按此算式可写出计算两个序列的最长公共子序列的长度函数。由于cij的产生仅依赖于 ci-1j-1、ci-1j和cij-1，故可以从cmn开始，跟踪cij的产生过程，逆向构造出 最长公共子序列。细节见程序。#include #include #define N 100char aN, bN, strN;int cNN;int lcs_len(char* a, char* b, int cN)int m = strlen(a), n

11、= strlen(b), i, j;for( i=0; i=m; i+ )ci0=0;for( i=0; i=n; i+ )c0i=0;for( i=1; i=m; i+ )for( j=1; j=cij-1)cij=ci-1j;elsecij=cij-1;return cmn;char* build_lcs(char s, char* a, char* b)int i = strlen(a), j = strlen(b);int k = lcs_len(a,b,c);sk = 0;while( k0 )if (cij=ci-1j)i-；else if (cij=cij-1)j-;elses-

12、k=ai-1;i-; j-;return s;void main()printf(Enter two string (length %d) :n,N);scanf(%s%s”,a,b);printf(LCS=%sn”,build_lcs(str,a,b);用动态规划实现导弹拦截某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个 缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的 高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统， 因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大

13、于30000的正整数），计算这套系 统最多能拦截多少导弹，并依次输出被拦截的导弹飞来时候的高度。SAMPLE INPUT:389 207 155 300 299 170 158 65SAMPLE OUTPUT:6389 300 299 170 158 65因为只有一套导弹拦截系统，并且这套系统除了第一发炮弹能到达任意高度外，以后的 每一发炮弹都不能高于前一发炮弹的高度；所以，被拦截的导弹应该按飞来的高度组成一 个非递增序列。题目要求我们计算这套系统最多能拦截的导弹数，并依次输出被拦截导弹的 高度，实际上就是要求我们在导弹依次飞来的高度序列中寻找一个最长非递增子序列。设X=x1,x 2，,x n

14、 )为依次飞来的导弹序列，Y=(y 1 ,y 2，,y k 为问题的最优解 (即X的最长非递增子序列)，s为问题的状态(表示导弹拦截系统当前发送炮弹能够到 达的最大高度，初值为s*第一发炮弹能够到达任意的高度)。如果y 1 =x 1，即飞 来的第一枚导弹被成功拦截。那么，根据题意“每一发炮弹都不能高于前一发的高度”，问题 的状态将由s=8变成sx 1 ( x 1为第一枚导弹的高度)；在当前状态下，序列Y 1 =y 2，,y k 也应该是序列X 1 =(x 2，,x n )的最长非递增子序列(大家用反证法很容易证 明)。也就是说，在当前状态s1。假设系统最多能拦截的导弹数为dmax (即问题的最

15、优值)，则dmax = max(D(i)所以，要计算问题的最优值dmax，需要分别计算出D(1)、D(2)、. D(n)的值， 然后将它们进行比较，找出其中的最大值。根据上面分析出来的递归方程，我们完全可以设 计一个递归函数，采用自顶向下的方法计算D(i)的值。然后，对i从1到n分别调用这 个递归函数，就可以计算出D(1)、D(2)、D(n)。但这样将会有大量的子问题被重 复计算。比如在调用递归函数计算D(1)的时候，可能需要先计算D(5)的值；之后在分别 调用递归函数计算D(2)、D(3)、D(4)的时候，都有可能需要先计算D(5)的值。如此 一来，在整个问题的求解过程中，D(5)可能会被重

16、复计算很多次，从而造成了冗余，降低 了程序的效率。其实，通过以上分析，我们已经知道：D(n)=1。如果将n作为阶段对问题进行划分， 根据问题的动态规划递归方程，我们可以采用自底向上的方法依次计算出D(n-1)、D(n-2)、D(1)的值。这样，每个D(i)的值只计算一次，并在计算的同时把计算结果 保存下来，从而避免了有些子问题被重复计算的情况发生，提高了程序的效率。算法代码如 下：for(i=n-2;i=0;i-)从后往前计算 di值for(j=i+1;jn;j+)if(arrayj=arrayi)&(didj+1)di=dj+1;dmax = 0;xh = 1;for(i=0;idmax)(

17、dmax = di;xh = i;coutdmaxendl;输出结果coutarrayxh);int temp = xh;for(i=xh+1;in;i+)if(di=dtemp-1)temp = i;coutarrayi;coutendl;最大化投资回报问题的实现最大化投资回报问题：某人有一定的资金用来购买不同面额的债卷，不同面额债卷的年收 益是不同的，求给定资金，年限以及债卷面额、收益的情况下怎样购买才能使此人获得最大 投资回报。程序输入约定：第一行第一列表示资金（1000的倍数）总量，第二列表示投资年限；第 二行表示债卷面额总数；从第三行开始每行表示一种债卷，占用两列，前一列表示债卷面额

18、， 后一列表示其年收益，如下输入实例，10000 124000 4003000 250程序实现如下，注释几乎说明了一切，所以不再另外分析。/此数组是算法的关键存储结构，用来存储不同阶段各种债卷/组合下对应可获取的最大利息。int saifa80005;III此函数用于计算当前债卷在不同购买额下的最优利息情况，/注意此时的利息情况是基于上一次债卷的情况下计算得到的，III也就是说当前利息最优是基于上一次利息最优的基础上计算出来的，/这也正好体现了动态规划中“最优化原则”：不管前面的策略如何，III此后的决策必须是基于当前状态(由上一次决策产生)的最优决策。/*动态规划的求解过程一般都可以用一个最

19、优决策表来描述，对于本程序，以示例输入为例，对于第一年，其最优决策表如下：0 1 2 3 4 5 6 7 8 9 10(*1000) - (1)0 0 0 0 400 400 400 400 800 800 800- (2)0 0 0 250 400 400 500 650 800 900 900- (3)(1) -表示首先选利息为400的债卷在对应资金下的最优利息。(2) -表示可用来购买债卷的资金。(3) -表示在已有状态下再选择利息为300的债卷在对应资金下的最优利息。注意上面表格，在求购买利息为300的债卷获得的最优收益的时候，参考了以前的最优状态，以3行8列的650为例，7(*100

20、0)可以在以前购买了 0张4000的债卷的基础上再2张3000的，也可以在以前购 买了 1张4000的基础上再买1张3000，经比较取其收益大的，这就是典 型的动态规划中的当前最优状态计算。本程序中把上面的最优决策二维表用一个一维数组表示，值得借鉴。*/void add(int a,int b)( cout a b endl; II for debugfor(int i=0;i 80000)break;if(saifai+b saifai+a) II累计同时购买多种债卷时的利息saifai+a = saifai + b;if(i200) II for debugcout i - saifai

21、;cout endl; II for debugint main(void)int n,d,money,year,pay,bond;int ii,i;scanf(%d”,&n);for(ii=0;iin;ii+)memset(saifa,0,sizeof(saifa);scanf(%d%d”,&money,&year);scanf(%d”,&d);for(i=0;id;i+)scanf(%d%d,&pay,&bond);add(pay/1000,bond);/计算指定年限内最优组合的本金利息总额for(i=0;iyear;i+) cout saifamoney/1000 ; / for debugmoney += saifamoney/1000;cout endl; / for debugprintf(%dn,money);return 0;上述程序实现方法同样适合于背包问题，最优库存问题等，只是针对具体情况，最优决 策表的表示和生成会有所不同。