数学研发论坛

 找回密码
 欢迎注册
楼主: kon3155

[分享] 经典算法普及——基础篇

[复制链接]
 楼主| 发表于 2009-2-25 14:08:39 | 显示全部楼层
【能量项链】
    在Mars星球上,每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是Mars人吸收能量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m,尾标记为r,后一颗能量珠的头标记为r,尾标记为n,则聚合后释放的能量为m*r*n(Mars单位),新产生的珠子的头标记为m,尾标记为n。
    需要时,Mars人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。
    例如:设N=4,4颗珠子的头标记与尾标记依次为(2,3) (3,5) (5,10) (10,2)。我们用记号⊕表示两颗珠子的聚合操作,(j⊕k)表示第j,k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为:
(4⊕1)=10*2*3=60。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4⊕1)⊕2)⊕3)=10*2*3+10*3*5+10*5*10=710。
【输入文件】
    输入文件energy.in的第一行是一个正整数N(4≤N≤100),表示项链上珠子的个数。第二行是N个用空格隔开的正整数,所有的数均不超过1000。第i个数为第i颗珠子的头标记(1≤i≤N),当i<N时,第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。
    至于珠子的顺序,你可以这样确定:将项链放到桌面上,不要出现交叉,随意指定第一颗珠子,然后按顺时针方向确定其他珠子的顺序。
【输出文件】
输出文件energy.out只有一行,是一个正整数E(E≤2.1*109),为一个最优聚合顺序所释放的总能量。
【输入样例】
4
2 3 5 10
【输出样例】
710

参考答案

【网上解题思路】
    简单的说:给你一项链,项链上有n颗珠子。相邻的两颗珠子可以合并(两个合并成一个)。合并的同时会放出一定的能量。不同的珠子的合并所释放的能量是不同的。问:按照怎样的次序合并才能使释放的能量最多?
  我们用top表示第i颗珠子的头标记,用wei表示第i颗珠子的尾标记,合并两颗相邻珠子所释放的能量是:
  Q=top*wei*wei[i+1]或top*top[i+1]*wei[i+1]; (一个样的)
  合并不一定按顺序的,本题所提供的样例也是导致出错的一大原因。
  n个珠子进行一次合并的后,就归结到了n-1个珠子的合并的问题。所以我们想到了动态规划。
  既然是dp题目,必然要满足dp的两大条件:、
  1.最优子结构性质;
  设Q[i,j]表示第i颗珠子到第j颗珠子合并所产生的能量。显然Q[1,n]表示的是合并产生的总的能量。给定一种标号方法,maxQ[1,n]就是所要求的。设最后一次合并在k处进行,则有Q[1,n]=Q[1,k]+Q[k+1,n]+top[1]*wei[k]*wei[n]。要Q[1,n]最大,必然要Q[1,k],Q[k+1,n]最大。
  证明:假设Q[1,k]不是最大,则必然存在一Q'[1,k]>Q[1,k]。
       那么就有Q'[1,n]=Q'[1,k]+Q[k+1,n]+top[1]*wei[k]*wei[n]>Q[1,k]。这与Q[1,n]的最优性矛盾。
  最优子结构性质得证。
   2.无后效性;
   无后效性是显然的,进行某次合并,合并前与合并后状态是相对独立,不相关联,互不影响的。
  
  算法已经定了下来了,关键是怎么实现了。
  项链是一个环,而我们处理是对一个串进行的。所以我们要把项链从某处割断展开,不同处的割断对应着不同的展开方法,也就是对应着不同的标号方法。产生的maxQ[1,n]也就不同的。所以我们要对这些maxQ[1,n]进行打擂,取其最大的一个,即为解了。
  dp的转移方程是:
   Best=maxQ[1,n] 1<=i<=n (i表示从第i颗珠子处展开,顺次标号);
   Q[i,j]=max{Q[i,k]+Q[k+1,j]+top*wei[k]*wei[j] 1<=i<=k<j<=n };
   其中Q[i,i]=0 1<=i<=n;
  dp的时间复杂度为O(n^3),n种的展开方法对应需要n次的dp,所以时间复杂度为O(n^4)。空间为O(n^2)。
  显然O(n^4)过这个题目是有点欠缺的,对的大的数据貌似很容易超时的。
  如果仔细想想,我们还是做了很不重复的工作的,不同的展开方式中必然存在着很多的大量的重复运算。于是还有很大的优化空间,既然展开做了很多的重复的工作,那么就合并起来吧。回到起点,开始的时候为什么我们要对项链做n次的展开呢,基于我们在运算的时候不能够实现第一颗珠子与第n颗珠子的相邻性。为了一次dp就实现所以的的珠子的相邻性,我们做如下处理:
    a[1],a[2],a[3]...a[n],a[1],a[2]...a[n-1] 
            (原来的)      (延伸的)

  也就是:
    a[1],a[2],a[3]...a[n],a[n+1],a[n+2]...a[m]   
  显然m=2n-1;
 我们对这一串珠子dp一次即可得解;dp方程为:
   Best=max{Q[i,i+n-1] 1<=i<=n}
    Q[i,j]=max{Q[i,k]+Q[k+1,j]+top*wei[k]*wei[j] 1<=i<=k<j<=min(i+n-1,m)}
  其中Q[i,i]=0 1<=i<=m;
  显然时间复杂度为O(n^3),空间为O(n^2)。min(i+n-1,m)已经对dp进行了优化。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 14:10:04 | 显示全部楼层
【0/1背包问题】
    在0/1背包问题中,需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品,每件物品i 的重量为wi ,价值为pi 。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高,即p1*x1+p2*x1+...+pi*xi(其1<=i<=n,x取0或1,取1表示选取物品i) 取得最大值。
【输入文件】
第一行一个数c,为背包容量。
第二行一个数n,为物品数量
第三行n个数,以空格间隔,为n个物品的重量
第四行n个数,以空格间隔,为n个物品的价值
【输出文件】
能取得的最大价值。
【分析】
    初看这类问题,第一个想到的会是贪心,但是贪心法却无法保证一定能得到最优解,看以下实例:
    贪心准则1:从剩余的物品中,选出可以装入背包的价值最大的物品,利用这种规则,价值最大的物品首先被装入(假设有足够容量),然后是下一个价值最大的物品,如此继续下去。这种策略不能保证得到最优解。例如,考虑n=2, w=[100,10,10], p =[20,15,15], c =105。当利用价值贪婪准则时,获得的解为x= [1,0,0],这种方案的总价值为20。而最优解为[0,1,1],其总价值为30。
    贪心准则2:从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解,但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时,获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。
    贪心准则3:价值密度pi /wi 贪婪算法,这种选择准则为:从剩余物品中选择可 装入包的pi /wi 值最大的物品,但是这种策略也不能保证得到最优解。利用此策略解 n=3 ,w=[20,15,15], p=[40,25,25], c=30 时的得到的就不是最优解。  
    由此我们知道无法使用贪心算法来解此类问题。我们采用如下思路:
    在该问题中需要决定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 ] 必须是第一次决策之后的一个最优方案。也就是说在此问题中,最优决策序列由最优决策子序列组成。
    假设f (i,j) 表示剩余容量为j,剩余物品为i,i + 1,...,n 时的最优解的值,即:利用最优序列由最优子序列构成的结论,可得到f 的递归式为:
  当j≥wi时: f(i,j)=max{f(i+1,j),f(i+1,j-wi)+pi}
    当0≤j<wi时:f(i,j)=f(i+1,j)
    这是一个递归的算法,其时间效率较低,为指数级。

    考虑用动态规划的方法来解决:
    阶段:在前i件物品中,选取若干件物品放入背包中;
    状态:在前i件物品中,选取若干件物品放入所剩空间为c的背包中的所能获得的最大价值;
    决策:第i件物品放或者不放;
    由此可以写出动态转移方程:
    用f[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值
              f[i,j]=max{f[i-1,j-wi]+pi (j>=wi), f[i-1,j]}
这样,就可以自底向上地得出在前n件物品中取出若干件放进背包能获得的最大价值,也就是f[n,c]

    算法框架如下:

  1.    for i:=0 to c do    {i=0也就是没有物品时清零}
  2.      f[0,i]:=0;
  3.    for i:=1 to n do    {枚举n件物品}
  4.      for j:=0 to c do  {枚举所有的装入情况}
  5.       begin
  6.        f[i,j]:=f[i-1,j];  {先让本次装入结果等于上次结果}
  7.        if (j>=w[i]) and (f[i-1,j-w[i]]+p[i]>f[i,j])   {如果能装第i件物品}
  8.          then f[i,j]:=f[i-1,j-w[i]]+p[i];             {且装入后价值变大则装入}  
  9.       end;
  10.    writeln(f[n,c]);
复制代码
为了进一步说明算法的执行原理,下面给出一个实例:
【输入文件】
10
4
5 1 4 3
40 10 25 30
【输出结果】下面列出所有的f[i,j]
0  0  0  0 40 40 40 40 40 40
10 10 10 10 40 50 50 50 50 50
10 10 10 25 40 50 50 50 65 75
10 10 30 40 40 50 55 70 80 80
从以上的数据中我们可以清晰地看到每一次的枚举结果,每一行都表示一个阶段。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 14:11:45 | 显示全部楼层
【开心的金明】
    金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N 元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的N 元。于是,他把每件物品规定了一个重要度,分为5 等:用整数1~5 表示,第5 等最重要。他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过N 元(可以等于N 元)的前提下,使每件物品的价格与重要度的乘积的总和最大。设第j 件物品的价格为v[j],重要度为w[j],共选中了k 件物品,编号依次为j1...jk,则所求的总和为:v[j1]*w[j1]+..+v[jk]*w[jk]请你帮助金明设计一个满足要求的购物单。
【输入文件】
输入的第1 行,为两个正整数,用一个空格隔开:
N m
(其中N(<30000)表示总钱数,m(<25)为希望购买物品的个数。)
从第2 行到第m+1 行,第j 行给出了编号为j-1的物品的基本数据,每行有2 个非负整数
v p
(其中v 表示该物品的价格(v≤10000),p 表示该物品的重要度(1~5))

【输出文件】
输出只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)。

【输入样例】
1000 5
800 2
400 5
300 5
400 3
200 2

【输出样例】
3900

【分析】
    典型的0/1背包问题,把总钱数N元当作背包容量,物品价格当作重量,重要度和价格的乘积当成参考价值,就可直接套用背包问题动态规划程序求解。
参考答案
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 14:12:51 | 显示全部楼层
【金明的预算方案】
    金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子:
主件 附件
电脑 打印机,扫描仪
书柜 图书
书桌 台灯,文具
工作椅 无
  如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的N元。于是,他把每件物品规定了一个重要度,分为5等:用整数1~5表示,第5等最重要。他还从因特网上查到了每件物品的价格(都是10元的整数倍)。他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。
  设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编号依次为j1,j2,……,jk,则所求的总和为:v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。(其中*为乘号)请你帮助金明设计一个满足要求的购物单。
【输入文件】
    输入文件的第1行,为两个正整数,用一个空格隔开: N m 其中N(<32000)表示总钱数,m(<60)为希望购买物品的个数。)
    从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有3个非负整数 v p q (其中v表示该物品的价格(v<10000),p表示该物品的重要度(1~5),q表示该物品是主件还是附件。如果q=0,表示该物品为主件,如果q>0,表示该物品为附件,q是所属主件的编号)
【输出文件】
输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值 (<200000)。

【输入样例】
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

【输出样例】
2200
【分析】
    简单方案:
    对每一个物品做两种决策,取与不取。如果取,满足两个条件:1.要么它是主件,要么它所属的主件已经在包里了。2.放进去后的重要度与价格的成绩的总和要比没放进时的大。这两个条件缺一不可的。于是得到如下的动规方程:
  f[i,j]:=f[i-1,j];
   if (i为主件 or i的主件在包中)and (f[i,j]<f[i,j-v]+v*w)
     then f[i,j]:=f[i,j-v]+v*w;
    注意题目中还有一个条件:“每件物品都是10元的整数倍”,利用它就可以把速度在提高十倍。

  改进方案:
    细细的看题目,还一个很重要的条件我们还没用:“每个主件可以有0个,1个或2个附件”。也就是说对于一套物品(包含主件,所有的附件),我们称为一个属类,对一个属类的物品的购买方法,有以下5种:
    1.一个都不买
    2.主件
    3.主件+附件1
    4.主件+附件2
    5.主件+附件1+附件2
  这五种购买方法也是唯一的五种方法,也就是说对一属类的物品,我们只有上述的5种购买方法。 于是我们很自然的就会想到把物品按物品的属类捆在一起考虑。这样我们把物品的属类作为dp的状态。可以得到如下的dp方程:
     f[i,j]=max{f[i-1,j];
   f[i-1,j-v[i,0]]+v[i,0]*w[i,0];
    f[i-1,j-v[i,0]-v[i,1]]+v[i,0]*w[i,0]+v[i,1]*w[i,1];
    f[i-1,j-v[i,0]-v[i,2]]+v[i,0]*w[i,0]+v[i,2]*w[i,2];
    f[i-1,j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]+v[i,2]*w[i,2];}
    这种方法的DP效率大大提高,不过需要对输入数据进行重新处理,使之按属类重新编号。
参考答案

[ 本帖最后由 kon3155 于 2009-2-25 15:28 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 14:14:21 | 显示全部楼层
【加分二叉树】
    设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第i个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下: subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数 若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出;
(1)tree的最高加分
(2)tree的前序遍历
【输入格式】
第1行:一个整数n(n<30),为节点个数。 第2行:n个用空格隔开的整数,为每个节点的分数(分数<100)。
【输出格式】
第1行:一个整数,为最高加分(结果不会超过4,000,000,000)。 第2行:n个用空格隔开的整数,为该树的前序遍历。
【输入样例】
5
5 7 1 2 10
【输出样例】
145
3 1 2 4 5
【分析】
    如果用数组value[i,j]表示从节点i到节点j所组成的二叉树的最大加分,则动态方程可以表示如下:
value[i,j]=max{value[i,i]+value[i+1,j],value[i+1,i+1]+value[i,i]*value[i+2,j], value[i+2,i+2]+value[i,i+1]*value[i+3,j],…,value[j-1,j-1]+value[i,j-2]*value[j,j], value[j,j]+value[i,j-1]}
    题目还要求输出最大加分树的前序遍历序列,因此必须在计算过程中记下从节点i到节点j所组成的最大加分二叉树的根节点,用数组root[i,j]表示

参考答案
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 14:14:59 | 显示全部楼层
【字串编辑距离】
    设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括 (1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符。将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离,记为 d(A,B)。试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离d(A,B)。

【输入格式】
输入的第一行是字符串A,文件的第二行是字符串B。

【输出格式】
程序运行结束时,将编辑距离d(A,B)输出。

【样例输入】
fxpimu
xwrs
【样例输出】
5

【参考解答】
////////////////////
Refrence : Dynamic Programming Algorithm (DPA) for Edit-Distance
编辑距离
关于两个字符串s1,s2的差别,可以通过计算他们的最小编辑距离来决定。
所谓的编辑距离: 让s1和s2变成相同字符串需要下面操作的最小次数。
1. 把某个字符ch1变成ch2
2. 删除某个字符
3. 插入某个字符
例如 s1 = “12433” 和s2=”1233”;
则可以通过在s2中间插入4得到12433与s1一致。
即 d(s1,s2) = 1 (进行了一次插入操作)
编辑距离的性质
计算两个字符串s1+ch1, s2+ch2的编辑距离有这样的性质:
1. d(s1,””) = d(“”,s1) = |s1| d(“ch1”,”ch2”) = ch1 == ch2 ? 0 : 1;
2. d(s1+ch1,s2+ch2) = min( d(s1,s2)+ ch1==ch2 ? 0 : 1 ,
d(s1+ch1,s2),
d(s1,s2+ch2) );
第一个性质是显然的。
第二个性质: 由于我们定义的三个操作来作为编辑距离的一种衡量方法。
于是对ch1,ch2可能的操作只有
1. 把ch1变成ch2
2. s1+ch1后删除ch1 d = (1+d(s1,s2+ch2))
3. s1+ch1后插入ch2 d = (1 + d(s1+ch1,s2))
对于2和3的操作可以等价于:
_2. s2+ch2后添加ch1 d=(1+d(s1,s2+ch2))
_3. s2+ch2后删除ch2 d=(1+d(s1+ch1,s2))
因此可以得到计算编辑距离的性质2。
复杂度分析
从上面性质2可以看出计算过程呈现这样的一种结构(假设各个层用当前计算的串长度标记,并假设两个串长度都为 n )
可以看到,该问题的复杂度为指数级别 3 的 n 次方,对于较长的串,时间上是无法让人忍受的。
分析: 在上面的结构中,我们发现多次出现了 (n-1,n-1), (n-1,n-2)……。换句话说该结构具有重叠子问题。再加上前面性质2所具有的最优子结构。符合动态规划算法基本要素。因此可以使用动态规划算法把复杂度降低到多项式级别。

  1. 动态规划求解
  2. 首先为了避免重复计算子问题,添加两个辅助数组。
  3. 一. 保存子问题结果。
  4. M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) 与 s2(0->j) 的编辑距离
  5. 二. 保存字符之间的编辑距离.
  6. E[ |s1|, |s2| ] , 其中 E[ i, j ] = s[i] = s[j] ? 0 : 1
  7. 三. 新的计算表达式
  8. 根据性质1得到
  9. M[ 0,0] = 0;
  10. M[ s1i, 0 ] = |s1i|;
  11. M[ 0, s2j ] = |s2j|;
  12. 根据性质2得到
  13. M[ i, j ] = min( m[i-1,j-1] + E[ i, j ] ,
  14. m[i, j-1] ,
  15. m[i-1, j] );
  16. 复杂度
  17. 从新的计算式看出,计算过程为
  18. i=1 -> |s1|
  19. j=1 -> |s2|
  20. M[i][j] = ……
  21. 因此复杂度为 O( |s1| * |s2| ) ,如果假设他们的长度都为n,则复杂度为 O(n^2)

  22. #include <stdio.h>
  23. #include <stdlib.h>
  24. #include <string.h>

  25. int _Min(int a,int b,int c)
  26. {
  27. int min=a;
  28. if (b <min)
  29. min=b;
  30. if(c <min)
  31. min=c;
  32. return min;
  33. }

  34. int ComputeDistance(char s[],char t[])
  35. {
  36. int n = strlen(s);

  37. int m = strlen(t);

  38. //int d[][] = new int[n + 1, m + 1]; // matrix
  39. int **d = (int **)malloc((n+1) * sizeof(int *));
  40. for(int i=0; i<=n; ++i)
  41. {
  42. d[i] = (int *)malloc((m+1) * sizeof(int));
  43. }
  44. // Step 1
  45. if (n == 0)
  46. {
  47. return m;
  48. }

  49. if (m == 0)
  50. {
  51. return n;
  52. }

  53. // Step 2
  54. for (int i = 0; i <= n; i++)
  55. {
  56. d[i][0] =i;
  57. }

  58. for (int j = 0; j <= m; d[0][j] = j++)
  59. {
  60. d[0][j] =j;
  61. }

  62. // Step 3
  63. for (int i = 1; i <= n; i++)
  64. {
  65. //Step 4
  66. for (int j = 1; j <= m; j++)
  67. {
  68. // Step 5
  69. int cost = (t[j-1] == s[i-1]) ? 0 : 1;

  70. // Step 6
  71. d[i][j] = _Min(d[i-1][j]+1, d[i][j-1]+1,d[i-1][j-1]+cost);
  72. }
  73. }
  74. // Step 7
  75. return d[n][m];
  76. }

  77. int main(int argc, char *argv[])
  78. {
  79. char a[9999];
  80. char b[9999];
  81. printf("请输入字符串1\n");
  82. scanf("%s",&a);
  83. printf("请输入字符串2\n");
  84. scanf("%s",&b);
  85. int result= ComputeDistance(a,b);
  86. printf("%d\n",result);
  87. system("PAUSE");
  88. return 0;
  89. }




复制代码

[ 本帖最后由 kon3155 于 2009-2-25 15:27 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 14:15:29 | 显示全部楼层
【花瓶插花】
    你想以最美观的方式布置花店的橱窗。你有F束花,每束花的品种都不一样,同时至少有同样数量的花瓶。它们被按顺序排成一排,花瓶的位置是固定的,并从左到右,从1 到 V编号,编号为V 的花瓶在最右边。花束可以移动,并且每束花用1到F的整数唯一标识。标识花束的整数决定了花束在花瓶中的排列的顺序,如果i<j,则花束i必须放在花束j左边的花瓶中。例如,假设杜鹃花的标识数为1,秋海棠的标识数为2,康乃馨的标识数为3,所有的花束在放入花瓶时必须保持其标识数的顺序,即:杜鹃花必须放在秋海棠左边的花瓶中。秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目,则多余的花瓶必须空,即每个花瓶只能放一束花。
   每一个花瓶的形状和颜色也不同,因此,当各个花瓶中放入不同的花束时,会产生不同的美学效果,并以美学值(一个整数)来表示,空花瓶的美学值为0。在上述例子中,花瓶与花束不同的搭配所具有的美学值,可以用如下的表格表示:
 花瓶 1 (杜鹃花) 2 (秋海棠) 3 (康乃馨)
1 7 5 -21
2 23 21 5
3 -5 -4 -4
4 -24 10 -20
5 16 23 20


    根据表格,杜鹃花放在花瓶2中,会显得非常好看,但若放你在花瓶4中则显得很难看。为了取得最佳美学效果,必须保持花束顺序的条件下,使花的摆放取得最大美学值,如果具有最大美学值的摆放不止一种,则输出任意一种。

【输入格式】
第一行包含两个数: F, V。(1<=F<=100, F<=V<=100 )
接下来的F行:包含V个数,输入Aij矩阵。 (-50<=Aij<=50,Aij为第i束花放在第j个花瓶中的美学值)

【输出格式】
第一行输出最大美学值
第二行给出方案

【输入样例】
3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20
【输出样例】
53
2 4 5

【参考程序】
  1. //:============================“插花问题”的动态规划法算法============================
  2. #define F 100
  3. #define V 100
  4. /**//*
  5.     插花问题描述:
  6.             将f束鲜花插入v个花瓶中,使达到最徍的视觉效果,
  7.         问题相关约定及插花要求:
  8.             鲜花被编号为1--f,花瓶被编号为1--v,花瓶按从小到
  9.         大顺序排列,一只花瓶只能插一支花,鲜花i插入花瓶j中的
  10.         视觉效果效果值已知,编号小的鲜花所放入的花瓶编号也小   
  11.     问题求解思路:
  12.             花瓶j(1<=j<=v)中插入鲜花的可能编号为[1..j](编号
  13.         小的鲜花所放入的花瓶编号也小);
  14.             设数组p[i][j]表示鲜花i插入花瓶j的好看程度,数组
  15.         q[i][j]表示[1..i]束鲜花插入[1..j]个花瓶所能得到的最大
  16.         好看程度,初始化q[0][0] = 0;q[0][j]=0(1<=j<=v),则q[f][v]
  17.         是问题的解.
  18.             特别地,j束鲜花插入到前面的j只花瓶中,所得到的好看
  19.         程度是q[j][j] = p[1][1]+p[2][2]+...+[j][j].现将插花过
  20.         程按花瓶排列顺序划分成不同阶段,则在第j阶段,第i束鲜花
  21.         若放入第j号花瓶,最大好看程度是q[i-1][j-1]+p[i][j];第i束鲜
  22.         花若放入前j-1个花瓶中的某一个,所得的好看程度是q[i][j-1],
  23.         那么在第j阶段,插入第i束鲜花所能得到的最大好看程度为:
  24.         q[i][j] = MAX(q[i-1][j-1]+p[i][j],q[i][j-1]),要使q[i][j]
  25.         最大,应使q[i-1][j-1]和q[i][j-1]也最大
  26. */
  27. #define MAX(A,B) ((A) > (B) ? (A):(B))        //求取两数的最大值宏定义
  28. #define F 100                    //鲜花数最大值常量定义
  29. #define V 100                    //花瓶数最大值常量定义
  30. //“插花问题”的初始化函数
  31. //    int    f,v:        鲜花数量,花瓶个数
  32. //    int    p[][v]:        鲜花i插入花瓶j的好看程度
  33. void Flower_Initialize(int *f,int *v,int p[][V])
  34. ...{
  35.     int i,j;
  36.     printf("输入鲜花数量及花瓶个数:");
  37.     scanf("%d%d",f,v);
  38.     printf("顺序输入各鲜花插入各花瓶的好看程度: ");
  39.     for(i=1;i<=*f;i++)
  40.         for(j=1;j<=*v;j++)
  41.             p[i][j] = i*j;
  42.             //scanf("%d",&p[i][j]);
  43. }
  44. //“插花问题”的动态规划法解决函数
  45. //    int    p[][v]:        鲜花i插入花瓶j的好看程度
  46. //    int    f,v:        鲜花数量,花瓶个数
  47. //    int    *way:        鲜花插入花瓶的插入方法结果
  48. int        Ikebana(int p[][V],int f,int v,int *way)
  49. ...{
  50.     int    i,j,q[F][V],newv;
  51.     q[0][0] = 0;    //初始化[没有一束花插入花瓶时],好看程度自然为0
  52.     //设置v个花瓶分别被插入v束鲜花时各号花瓶对应的(初始)最大好看程度
  53.     for(j = 1;j <= v;j++)
  54.     ...{
  55.         q[0][j] = 0;
  56.         //设置第j束鲜花放入第j号花瓶中的最大好看程度
  57.         q[j][j] = q[j - 1][j - 1] + p[j][j];
  58.     }
  59.     for(j = 1;j <= v;j++)
  60.         for(i = 1;i < j;i++)    //计算在第j阶段,插入第i束鲜花所能得到的最大好看程度
  61.             q[i][j] = MAX(q[i - 1][j - 1] + p[i][j],q[i][j - 1]);
  62.     newv = v;
  63.     for(i = f;i > 0;i--)
  64.     ...{
  65.         while(q[i-1][newv-1]+p[i][newv] < q[i][newv])
  66.             newv--;
  67.         //确定鲜花i插在花瓶newv中,并准备考虑前一只花瓶
  68.         way[i] = newv--;
  69.     }
  70.     return(q[f][v]);
  71. }
  72. //测试“插花问题”的动态规划法函数
  73. void    Run_Ikebana()
  74. ...{
  75.     //循环计数器,鲜花数量,花瓶个数,鲜花i插入花瓶j的好看程度,鲜花插入花瓶的插入方法结果
  76.     int    i,f,v,p[F][V],way[F];
  77.     Flower_Initialize(&f,&v,p);
  78.     printf("最大好看程度点数为%d ",Ikebana(p,f,v,way));
  79.     printf("插有鲜花的花瓶是: ");
  80.     for(i = 1;i <= f;i++)
  81.         printf("%4d",way[i]);
  82. }
  83. //:============================“插花问题”的动态规划法算法============================
  84. int main(int argc, char* argv[])
  85. ...{
  86.     //Run_SubString();
  87.     Run_Ikebana();
  88.     printf(" 应用程序运行结束! ");
  89.     return 0;
  90. }
复制代码

[ 本帖最后由 kon3155 于 2009-2-25 14:36 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 14:15:51 | 显示全部楼层
【凸多边形三角划分】
    给定一个具有N(N<50)个顶点(从l到N编号)的凸多边形,每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形,使得这些三角形顶点的权的乘积之和最小。
【输入格式】
第一行为顶点数N;
第二行为N个顶点(从1到N)的权值。
【输出格式】
最小的和的值。

【输入样例】
5
121 122 123 245 231
【输出样例】
12214884

【试题分析】
这是一道很典型的动态规划问题。设F[I,J](I<J)表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积,我们可以得到下面的动态转移方程:
F[I,J]=Min{F[I,K]+F[K,J]+S[I]*S[J]*S[K]}     (I<K<J)
目标状态为:F[1,N]
但我们可以发现,由于这里为乘积之和,在输入数据较大时有可能超过长整形甚至实形的范围,所以我们还需用高精度计算,但这是大家的基本功,程序中就没有写了,请读者自行完成。
【三】参考程序
  1. Var S                          :Array[1..50] Of Integer;
  2.     F                          :Array[1..50,1..50] Of Comp; 
  3.     D                     :Array[1..50,1..50] Of Byte;
  4.     N                     :Integer;
  5. Procedure Init;    (输入数据)
  6. Var I                          :Integer;
  7. Begin
  8.   Readln(N);
  9.   For I:=1 To N Do Read(S[I]);
  10. End;
  11. Procedure Dynamic;   (动态规划)
  12. Var I,J,K                  :Integer;
  13. Begin
  14.   For I:=1 To N Do
  15.     For J:=I+1 To N Do F[I,J]:=Maxlongint; (赋初始值)
  16.   For I:=N-2 Downto 1 Do
  17.     For J:=I+2 To N Do
  18.       For K:=I+1 To J-1 Do       
  19.         If (F[I,J]>F[I,K]+F[K,J]+S[I]*S[J]*S[K]) Then
  20.           Begin
  21.             F[I,J]:=F[I,K]+F[K,J]+S[I]*S[J]*S[K];
  22.             D[I,J]:=K;     (记录父节点)
  23.           End;           
  24. End;
  25. Procedure Print(I,J:Integer);  (输出每个三角形)
  26. Begin
  27.   If J=I+1 Then Exit;
  28.   Write(',',I,' ',J,' ',D[I,J]);
  29.   Out(I,D[I,J]);
  30.   Out(D[I,J],J);
  31. End;
  32. Procedure Out;  (输出信息)
  33. Begin
  34.   Assign(Output,'Output.Txt'); Rewrite(Output);
  35.   Writeln('The minimum is :',F[1,N]:0:0);
  36.   Writeln('The formation of ',N-2,' triangle:');
  37.   Write(1,' ',N,' 'D[1,N]);
  38.   Out(1,D[1,N]);
  39.   Out(D[1,N],N);
  40.   Close(Output);
  41. End;
  42. Begin  (主程序)
  43.   Init;
  44.   Dynamic;
  45.   Out;
  46. End.
复制代码

[ 本帖最后由 kon3155 于 2009-2-25 14:51 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 14:16:13 | 显示全部楼层
【快餐店】
    Peter最近在R市开了一家快餐店,为了招揽顾客,该快餐店准备推出一种套餐,该套餐由A个汉堡、B个薯条和C个饮料组成。价格便宜。为了提高产量,Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡、薯条和饮料,由于每条生产线每天所能提供的生产时间是有限的、不同的,而汉堡、薯条和饮料的单位生产时间又不同。这使得Peter很为难,不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序,计算一天中套餐的最大生产量。为简单起见,假设汉堡、薯条和饮料的日产量不超过100个。
【输入格式】
输入文件共四行。第一行为三个不超过100的正整数A B C,分别表示该套餐汉堡、薯条和饮料的数量,中间以一个空格分开。第二行为3个不超过100的正整数P1,P2,P3分别为汉堡、薯条和饮料的单位生产耗时,中间以一个空格分开。第三行为生产线条数N(0≤N≤10),第四行为N个不超过10000的正整数,分别为各条生产流水线每天提供的生产时间,中间以一个空格分开。
【输出格式】
输出文件仅一行,即每天套餐的最大产量。

【输入样例】
2 2 2
1 2 2
2
6 6
【输出样例】
1


【二】分析
本题是一个非常典型的资源分配问题。由于每条生产线的生产是相互独立,不互相影响的,所以此题可以以生产线为阶段用动态规划求解。
状态表示: 用p[I,j,k]表示前I条生产线生产j个汉堡,k个薯条的情况下最多可生产饮料的个数。
用r[I,j,k]表示第I条生产线生产j个汉堡,k个薯条的情况下最多可生产饮料的个数。
态转移方程 : p[I,j,k] = Max{p[I-1,j1,k1]+r[I,j-j1,k-k1]}
(0<=j1<=j,0<=k1<=k,且(j-j1)*p1+(k-k1)*p2<= 第I条生产线的生产时间)
但这样的算法是非常粗糙的,稍加分析可以发现,此算法的时间复杂度为O(N*1004),当N=10的时候,时间复杂度将达到10*1004=109,这是根本无法承受的。
于是,我们必须对算法进行进一步的优化,经仔细观察可以发现:这道题中存在着一个上限值(Min{100 div A, 100 div B, 100 div C}),这是一个很好的判断条件,他可以帮我们尽早地求出最优解。为什么这样说呢?因为,在动态规划开始前,我们可以先用贪心法算出N条生产线可以生产的套数,如果大于上限值则可以直接输出上限值并退出。否则再调用动态规划,而在动态规划求解的过程中,也可以在每完成一阶段工作便和上限值进行比较,若大于等于上限值就退出,这样一来,就可以尽早的求出解并结束程序。
具体的算法流程为:


【三】小结
动态规划虽然是种高效的算法,但不加优化的话,有可能在时间和空间上仍然有问题,因此,在做题时要充分发掘题目中的隐含条件,并充分利用已知条件,这样才能令程序更快,更优。

【四】对程序优化的进一步讨论:
   本题在具体实现中还有一些优化的余地,在此提出,以供参考:
(1)        存储结构:由于每一阶段状态只与上一阶段状态有关,所以我们可以只用两个100*100的数组滚动实现。但考虑到滚动是有大量的赋值,可以改进为动态数组,每次交换时只需交换指针即可,这样比原来数组间赋值要快。
(2)        减少循环:在计算每一阶段状态过程中无疑要用到4重循环,其实这当中有很多是可以省掉的,我们可以这样修改每一重循环的起始值:
原起始值:                       改进后的起始值:
for I := 1 to n do begin               for I := 1 to n do begin
  for j := 0 to tot[I] div p1 do          for j := 0 to min(q1,tot[I] div p1) do
for k := 0 to (tot[I]-p1*j) div p2 do     for k := 0 to min(q2,(tot[I]-p1*j) div p2) do
  for j1:=0 to j do                    for j1 := max(0,j-t[I] div p1) to
min(j,tot[I-1] div p1) do
        for k1 := 0 to k do                  for k1 := max(0,k-(t[I]-(j-j1)*p1) div p2)
to min(k,(tot[I-1]-p1*j1)div p2) do
{ 注:具体变量用途请参考程序 }
【五】参考程序
  1. {\$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
  2. {\$M 65520,0,655360}

  3. program FastFood;
  4. const
  5.    input      = 'input2.txt';
  6.  output     = 'output2.txt';
  7. var
  8.    f        : text;
  9.    r,p,pp    : array[0..100,0..100] of integer;  {pp:滚动数组中存放前一阶段的数组}
  10.    t,tot,tt    : array[0..10] of longint;  {tt:辅助数组;t:每条生产线的生产线时间;
  11. tot:1-I条生产线生产时间的总和}
  12.    n,a,b,c,p1,p2,p3   : longint;   {a,b,c:汉堡,薯条,饮料的个数;
  13. p1,p2,p3汉堡,薯条,饮料的生产单位耗时}

  14. procedure init;
  15.   var
  16.     i                           : integer;
  17.   begin
  18.     assign(f,input);
  19.     reset (f);
  20.     readln(f,a,b,c);
  21.     readlN(f,p1,p2,p3);
  22.     readln(f,n);
  23.     for i := 1 to n do read(f,t[i]);
  24.     close (f);
  25.     if n=0 then begin  { 特殊情况处理 }
  26.        assign(f,output);
  27.        rewrite(f);
  28.        writeln(f,0);
  29.        close (f);
  30.        halt;
  31.     end;
  32.   end;

  33. function  min(i,j : longint) : longint;   {求两数中较小的一个}
  34.   begin
  35.        if i>j then min := j else min := i;
  36.   end;

  37. function  max(i,j : longint) : longint;   {求两数中较大的一个}

  38.   begin
  39.        if i>j then max := i else max := j;
  40.   end;

  41. procedure main;
  42.   var
  43.     q,q1,q2,i,j,k,j1,k1                 : longint;  {q:上限值;q1,q2 : A,B的上限值}
  44.   begin
  45.     q := min( 100 div a,min( 100 div b, 100 div c ) ); {求上限值}
  46.     q1 := q*a;
  47.     q2 := q*b;
  48.     tt := t;
  49.     i := 1;
  50.     j := q1*p1;
  51.     while (j>0) and (i<=n) do   { 用贪心法求出N条生产线可以生产的套数(可行解)}
  52.           if j>tt[i] then begin
  53.              dec(j,tt[i]);  tt[i] := 0; inc(i);
  54.           end
  55.           else begin dec(tt[i],j); j := 0; end;
  56.     if j=0 then begin
  57.        j := q2*p2;
  58.        while (j>0) and (i<=n) do
  59.              if j>tt[i] then begin
  60.                 dec(j,tt[i]) ;tt[i] := 0; inc(i);
  61.              end
  62.              else begin dec(tt[i],j); j := 0; end;
  63.        if j=0 then begin  {如果可行,直接输出上限值}
  64.           assign(f,output);
  65.           rewrite(f);
  66.           writeln(f,q);
  67.           close (f);
  68.           halt;
  69.        end;
  70.     end;
  71.     tot[0] := 0;
  72.     for i := 1 to n do tot[i] := tot[i-1] + t[i];
  73.     if tot[n] div (a*p1+b*p2+c*p3)<q then begin  {否则修改上限值}
  74.        q := tot[n] div (a*p1+b*p2+c*p3);
  75.        q1 := q*a;
  76.        q2 := q*b;
  77.     end;
  78.     for i := 1 to n do begin
  79.         for j := 0 to min(q1,t[i] div p1) do
  80.             for k := 0 to min(q2,(t[i]-p1*j) div p2) do
  81.                 r[j,k] := (t[i]-p1*j-p2*k) div p3;
  82.         fillchar(p,sizeof(p),0);                  {数组清零}
  83.         for j := 0 to min(q1,tot[i] div p1) do  
  84.             for k := 0 to min(q2,(tot[i]-p1*j) div p2) do
  85.              for j1 := max(0,j-t[i] div p1) to min(j,tot[i-1] div p1) do
  86.               for k1 := max(0,k-(t[i]-(j-j1)*p1) div p2) to min(k,(tot[i-1]-p1*j1) div p2) do
  87.                  if p[j,k] < pp[j1,k1] + r[j-j1,k-k1] then
  88.                      p[j,k] := pp[j1,k1] + r[j-j1,k-k1];
  89.         if p[q*a,q*b]>=q*c then begin
  90.    {如果在此阶段产生了不小于上限值的解,则之际输出上限值,并直接退出}
  91.            assign(f,output);
  92.            rewrite(f);
  93.            writeln(f,q);
  94.            close (f);
  95.            halt;
  96.         end;
  97.         pp := p;
  98.         for j := 0 to min(100,tot[i] div p1) do
  99.             for k := 0 to min(100,(tot[i]-p1*j) div p2) do
  100.                 if p[j,k] > 100 then p[j,k] := 100;
  101.     end;
  102.     { out }
  103.     k1 := 0;               { 输出最优值  }
  104.     for j := 0 to 100 do
  105.         if (j div a > k1) then
  106.            for k := 0 to 100 do
  107.                if (k div b > k1) and (p[j,k] div c > k1 ) then
  108.                   k1 := min( min( j div a, k div b), p[j,k] div c );
  109.     assign(f,output);
  110.     rewrite(f);
  111.     writeln(f,k1);
  112.     close (f);
  113.   end;

  114. begin
  115.    init;
  116.    main;
  117. end.
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-25 15:18:59 | 显示全部楼层
辛苦了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-7-1 10:37 , Processed in 0.098759 second(s), 14 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表