经典算法普及——基础篇

kon3155

【能量项链】 在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颗珠子。相邻的两颗珠子可以合并(两个合并成一个)。合并的同时会放出一定的能量。不同的珠子的合并所释放的能量是不同的。问：按照怎样的次序合并才能使释放的能量最多？ 　　我们用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

kon3155

【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-1,j]} 这样，就可以自底向上地得出在前n件物品中取出若干件放进背包能获得的最大价值，也就是f[n,c] 算法框架如下：

2. for i:=0 to c do {i=0也就是没有物品时清零}
3. f[0,i]:=0;
4. for i:=1 to n do {枚举n件物品}
5. for j:=0 to c do {枚举所有的装入情况}
6. begin
7. f[i,j]:=f[i-1,j]; {先让本次装入结果等于上次结果}
8. if (j>=w[i]) and (f[i-1,j-w[i]]+p[i]>f[i,j]) {如果能装第i件物品}
9. then f[i,j]:=f[i-1,j-w[i]]+p[i]; {且装入后价值变大则装入}
10. end;
11. 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 从以上的数据中我们可以清晰地看到每一次的枚举结果，每一行都表示一个阶段。

kon3155

【开心的金明】 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过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元当作背包容量，物品价格当作重量，重要度和价格的乘积当成参考价值，就可直接套用背包问题动态规划程序求解。 【参考答案】

kon3155

【金明的预算方案】 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过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]参考答案】 [ 本帖最后由 kon3155 于 2009-2-25 15:28 编辑 ]

kon3155

【加分二叉树】 设一个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]表示 【参考答案】

kon3155

【字串编辑距离】 设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所具有的最优子结构。符合动态规划算法基本要素。因此可以使用动态规划算法把复杂度降低到多项式级别。

2. 动态规划求解
3. 首先为了避免重复计算子问题，添加两个辅助数组。
4. 一. 保存子问题结果。
5. M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) 与 s2(0->j) 的编辑距离
6. 二. 保存字符之间的编辑距离.
7. E[ |s1|, |s2| ] , 其中 E[ i, j ] = s[i] = s[j] ? 0 : 1
8. 三. 新的计算表达式
9. 根据性质1得到
10. M[ 0,0] = 0;
11. M[ s1i, 0 ] = |s1i|;
12. M[ 0, s2j ] = |s2j|;
13. 根据性质2得到
14. M[ i, j ] = min( m[i-1,j-1] + E[ i, j ] ,
15. m[i, j-1] ,
16. m[i-1, j] );
17. 复杂度
18. 从新的计算式看出，计算过程为
19. i=1 -> |s1|
20. j=1 -> |s2|
21. M[i][j] = ……
22. 因此复杂度为 O( |s1| * |s2| ) ，如果假设他们的长度都为n，则复杂度为 O(n^2)
24. #include <stdio.h>
25. #include <stdlib.h>
26. #include <string.h>
28. int _Min(int a,int b,int c)
29. {
30. int min=a;
31. if (b <min)
32. min=b;
33. if(c <min)
34. min=c;
35. return min;
36. }
38. int ComputeDistance(char s[],char t[])
39. {
40. int n = strlen(s);
42. int m = strlen(t);
44. //int d[][] = new int[n + 1, m + 1]; // matrix
45. int **d = (int **)malloc((n+1) * sizeof(int *));
46. for(int i=0; i<=n; ++i)
47. {
48. d[i] = (int *)malloc((m+1) * sizeof(int));
49. }
50. // Step 1
51. if (n == 0)
52. {
53. return m;
54. }
56. if (m == 0)
57. {
58. return n;
59. }
61. // Step 2
62. for (int i = 0; i <= n; i++)
63. {
64. d[i][0] =i;
65. }
67. for (int j = 0; j <= m; d[0][j] = j++)
68. {
69. d[0][j] =j;
70. }
72. // Step 3
73. for (int i = 1; i <= n; i++)
74. {
75. //Step 4
76. for (int j = 1; j <= m; j++)
77. {
78. // Step 5
79. int cost = (t[j-1] == s[i-1]) ? 0 : 1;
81. // Step 6
82. d[i][j] = _Min(d[i-1][j]+1, d[i][j-1]+1,d[i-1][j-1]+cost);
83. }
84. }
85. // Step 7
86. return d[n][m];
87. }
89. int main(int argc, char *argv[])
90. {
91. char a[9999];
92. char b[9999];
93. printf("请输入字符串1\n");
94. scanf("%s",&a);
95. printf("请输入字符串2\n");
96. scanf("%s",&b);
97. int result= ComputeDistance(a,b);
98. printf("%d\n",result);
99. system("PAUSE");
100. return 0;
101. }

复制代码

[ 本帖最后由 kon3155 于 2009-2-25 15:27 编辑 ]

kon3155

【花瓶插花】 你想以最美观的方式布置花店的橱窗。你有F束花，每束花的品种都不一样，同时至少有同样数量的花瓶。它们被按顺序排成一排，花瓶的位置是固定的，并从左到右，从1 到 V编号，编号为V 的花瓶在最右边。花束可以移动，并且每束花用1到F的整数唯一标识。标识花束的整数决定了花束在花瓶中的排列的顺序，如果i

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 编辑 ]

kon3155

【凸多边形三角划分】 给定一个具有N(N<50)个顶点(从l到N编号)的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小。 【输入格式】 第一行为顶点数N； 第二行为N个顶点(从1到N)的权值。 【输出格式】 最小的和的值。 【输入样例】 5 121 122 123 245 231 【输出样例】 12214884 【试题分析】 这是一道很典型的动态规划问题。设F[I,J]（I

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 编辑 ]

kon3155

【快餐店】 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}
4. program FastFood;
5. const
6. input = 'input2.txt';
7. 　output = 'output2.txt';
8. var
9. f : text;
10. r,p,pp : array[0..100,0..100] of integer;　　｛pp:滚动数组中存放前一阶段的数组｝
11. t,tot,tt : array[0..10] of longint; {tt:辅助数组；t:每条生产线的生产线时间；
12. tot:1-I条生产线生产时间的总和}
13. n,a,b,c,p1,p2,p3 : longint; {a,b,c:汉堡，薯条，饮料的个数；
14. p1,p2,p3汉堡，薯条，饮料的生产单位耗时}
16. procedure init;
17. var
18. i : integer;
19. begin
20. assign(f,input);
21. reset (f);
22. readln(f,a,b,c);
23. readlN(f,p1,p2,p3);
24. readln(f,n);
25. for i := 1 to n do read(f,t[i]);
26. close (f);
27. if n=0 then begin { 特殊情况处理 }
28. assign(f,output);
29. rewrite(f);
30. writeln(f,0);
31. close (f);
32. halt;
33. end;
34. end;
36. function min(i,j : longint) : longint; {求两数中较小的一个}
37. begin
38. if i>j then min := j else min := i;
39. end;
41. function max(i,j : longint) : longint; {求两数中较大的一个}
43. begin
44. if i>j then max := i else max := j;
45. end;
47. procedure main;
48. var
49. q,q1,q2,i,j,k,j1,k1 : longint; {q:上限值；q1,q2 : A,B的上限值}
50. begin
51. q := min( 100 div a,min( 100 div b, 100 div c ) ); {求上限值}
52. q1 := q*a;
53. q2 := q*b;
54. tt := t;
55. i := 1;
56. j := q1*p1;
57. while (j>0) and (i<=n) do { 用贪心法求出N条生产线可以生产的套数（可行解）}
58. if j>tt[i] then begin
59. dec(j,tt[i]); tt[i] := 0; inc(i);
60. end
61. else begin dec(tt[i],j); j := 0; end;
62. if j=0 then begin
63. j := q2*p2;
64. while (j>0) and (i<=n) do
65. if j>tt[i] then begin
66. dec(j,tt[i]) ;tt[i] := 0; inc(i);
67. end
68. else begin dec(tt[i],j); j := 0; end;
69. if j=0 then begin {如果可行，直接输出上限值}
70. assign(f,output);
71. rewrite(f);
72. writeln(f,q);
73. close (f);
74. halt;
75. end;
76. end;
77. tot[0] := 0;
78. for i := 1 to n do tot[i] := tot[i-1] + t[i];
79. if tot[n] div (a*p1+b*p2+c*p3)<q then begin {否则修改上限值}
80. q := tot[n] div (a*p1+b*p2+c*p3);
81. q1 := q*a;
82. q2 := q*b;
83. end;
84. for i := 1 to n do begin
85. for j := 0 to min(q1,t[i] div p1) do
86. for k := 0 to min(q2,(t[i]-p1*j) div p2) do
87. r[j,k] := (t[i]-p1*j-p2*k) div p3;
88. fillchar(p,sizeof(p),0); {数组清零}
89. for j := 0 to min(q1,tot[i] div p1) do
90. for k := 0 to min(q2,(tot[i]-p1*j) div p2) do
91. for j1 := max(0,j-t[i] div p1) to min(j,tot[i-1] div p1) do
92. for k1 := max(0,k-(t[i]-(j-j1)*p1) div p2) to min(k,(tot[i-1]-p1*j1) div p2) do
93. if p[j,k] < pp[j1,k1] + r[j-j1,k-k1] then
94. p[j,k] := pp[j1,k1] + r[j-j1,k-k1];
95. if p[q*a,q*b]>=q*c then begin
96. {如果在此阶段产生了不小于上限值的解，则之际输出上限值，并直接退出}
97. assign(f,output);
98. rewrite(f);
99. writeln(f,q);
100. close (f);
101. halt;
102. end;
103. pp := p;
104. for j := 0 to min(100,tot[i] div p1) do
105. for k := 0 to min(100,(tot[i]-p1*j) div p2) do
106. if p[j,k] > 100 then p[j,k] := 100;
107. end;
108. { out }
109. k1 := 0; { 输出最优值 }
110. for j := 0 to 100 do
111. if (j div a > k1) then
112. for k := 0 to 100 do
113. if (k div b > k1) and (p[j,k] div c > k1 ) then
114. k1 := min( min( j div a, k div b), p[j,k] div c );
115. assign(f,output);
116. rewrite(f);
117. writeln(f,k1);
118. close (f);
119. end;
121. begin
122. init;
123. main;
124. end.

复制代码

g99

辛苦了