【能量项链】
在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或top*top*wei; （一个样的）
合并不一定按顺序的，本题所提供的样例也是导致出错的一大原因。
n个珠子进行一次合并的后，就归结到了n-1个珠子的合并的问题。所以我们想到了动态规划。
既然是dp题目，必然要满足dp的两大条件：、
1.最优子结构性质；
设Q表示第i颗珠子到第j颗珠子合并所产生的能量。显然Q表示的是合并产生的总的能量。给定一种标号方法，maxQ就是所要求的。设最后一次合并在k处进行，则有Q＝Q＋Q＋top*wei*wei。要Q最大，必然要Q，Q最大。
证明：假设Q不是最大，则必然存在一Q'>Q。
那么就有Q'＝Q'＋Q＋top*wei*wei>Q。这与Q的最优性矛盾。
最优子结构性质得证。
2.无后效性；
无后效性是显然的，进行某次合并，合并前与合并后状态是相对独立，不相关联，互不影响的。
算法已经定了下来了，关键是怎么实现了。
项链是一个环，而我们处理是对一个串进行的。所以我们要把项链从某处割断展开，不同处的割断对应着不同的展开方法，也就是对应着不同的标号方法。产生的maxQ也就不同的。所以我们要对这些maxQ进行打擂，取其最大的一个，即为解了。
dp的转移方程是：
Best=maxQ 1<=i<=n (i表示从第i颗珠子处展开，顺次标号）；
Q=max{Q+Q+top*wei*wei 1<=i<=k<j<=n };
其中Q=0 1<=i<=n;
dp的时间复杂度为O(n^3)，n种的展开方法对应需要n次的dp，所以时间复杂度为O(n^4)。空间为O(n^2)。
显然O(n^4)过这个题目是有点欠缺的，对的大的数据貌似很容易超时的。
如果仔细想想，我们还是做了很不重复的工作的，不同的展开方式中必然存在着很多的大量的重复运算。于是还有很大的优化空间，既然展开做了很多的重复的工作，那么就合并起来吧。回到起点，开始的时候为什么我们要对项链做n次的展开呢，基于我们在运算的时候不能够实现第一颗珠子与第n颗珠子的相邻性。为了一次dp就实现所以的的珠子的相邻性，我们做如下处理：
a,a,a...a,a,a...a
（原来的） （延伸的）
也就是：
a,a,a...a,a,a...a
显然m=2n-1;
我们对这一串珠子dp一次即可得解；dp方程为：
Best=max{Q 1<=i<=n}
Q=max{Q+Q+top*wei*wei 1<=i<=k<j<=min(i+n-1,m)}
其中Q=0 1<=i<=m;
显然时间复杂度为O(n^3)，空间为O(n^2)。min(i+n-1,m)已经对dp进行了优化。
【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=, p =, c =105。当利用价值贪婪准则时，获得的解为x= ，这种方案的总价值为20。而最优解为，其总价值为30。
贪心准则2：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=, p=, c= 2 5。当利用重量贪婪策略时，获得的解为x =, 比最优解[ 0 , 1 ]要差。
贪心准则3：价值密度pi /wi 贪婪算法，这种选择准则为：从剩余物品中选择可 装入包的pi /wi 值最大的物品，但是这种策略也不能保证得到最优解。利用此策略解 n=3 ,w=, p=, 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， 必须是第一次决策之后的一个最优方案。也就是说在此问题中，最优决策序列由最优决策子序列组成。
假设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 的背包里所能获得的最大价值
f=max{f+pi (j>=wi), f}
这样，就可以自底向上地得出在前n件物品中取出若干件放进背包能获得的最大价值，也就是f
算法框架如下：
for i:=0 to c do {i=0也就是没有物品时清零}
f:=0;
for i:=1 to n do {枚举n件物品}
for j:=0 to c do{枚举所有的装入情况}
begin
f:=f;{先让本次装入结果等于上次结果}
if (j>=w) and (f]+p>f) {如果能装第i件物品}
then f:=f]+p; {且装入后价值变大则装入}
end;
writeln(f);
为了进一步说明算法的执行原理，下面给出一个实例：
【输入文件】
10
4
5 1 4 3
40 10 25 30
【输出结果】下面列出所有的f
0000 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
从以上的数据中我们可以清晰地看到每一次的枚举结果，每一行都表示一个阶段。
【开心的金明】
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。于是，他把每件物品规定了一个重要度，分为5 等：用整数1~5 表示，第5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j 件物品的价格为v，重要度为w，共选中了k 件物品，编号依次为j1...jk，则所求的总和为：v*w+..+v*w请你帮助金明设计一个满足要求的购物单。
【输入文件】
输入的第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元当作背包容量，物品价格当作重量，重要度和价格的乘积当成参考价值，就可直接套用背包问题动态规划程序求解。
【参考答案】
【金明的预算方案】
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件 附件
电脑 打印机，扫描仪
书柜 图书
书桌 台灯，文具
工作椅 无
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v，重要度为w，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v*w+v*w+ …+v*w。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。
【输入文件】
输入文件的第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:=f;
if (i为主件 or i的主件在包中）and (f<f+v*w)
then f:=f+v*w;
注意题目中还有一个条件：“每件物品都是10元的整数倍”，利用它就可以把速度在提高十倍。
改进方案：
细细的看题目，还一个很重要的条件我们还没用：“每个主件可以有０个，１个或２个附件”。也就是说对于一套物品（包含主件，所有的附件），我们称为一个属类，对一个属类的物品的购买方法，有以下５种：
１.一个都不买
２.主件
３.主件＋附件１
４.主件＋附件２
５.主件＋附件１＋附件２
这五种购买方法也是唯一的五种方法，也就是说对一属类的物品，我们只有上述的５种购买方法。 于是我们很自然的就会想到把物品按物品的属类捆在一起考虑。这样我们把物品的属类作为dp的状态。可以得到如下的dp方程：
f=max{f;
f]+v*w;
f-v]+v*w+v*w;
f-v]+v*w+v*w;
f-v-v]+v*w+v*w+v*w;}
这种方法的DP效率大大提高，不过需要对输入数据进行重新处理，使之按属类重新编号。
【参考答案】
[ 本帖最后由 kon3155 于 2009-2-25 15:28 编辑 ]
【加分二叉树】
设一个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所组成的二叉树的最大加分，则动态方程可以表示如下：
value=max{value+value,value+value*value, value+value*value,…,value+value*value, value+value}
题目还要求输出最大加分树的前序遍历序列，因此必须在计算过程中记下从节点i到节点j所组成的最大加分二叉树的根节点，用数组root表示
【参考答案】
【字串编辑距离】
设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所具有的最优子结构。符合动态规划算法基本要素。因此可以使用动态规划算法把复杂度降低到多项式级别。
动态规划求解
首先为了避免重复计算子问题，添加两个辅助数组。
一. 保存子问题结果。
M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) 与 s2(0->j) 的编辑距离
二. 保存字符之间的编辑距离.
E[ |s1|, |s2| ] , 其中 E[ i, j ] = s = s ? 0 : 1
三. 新的计算表达式
根据性质1得到
M[ 0,0] = 0;
M[ s1i, 0 ] = |s1i|;
M[ 0, s2j ] = |s2j|;
根据性质2得到
M[ i, j ] = min( m + E[ i, j ] ,
m ,
m );
复杂度
从新的计算式看出，计算过程为
i=1 -> |s1|
j=1 -> |s2|
M = ……
因此复杂度为 O( |s1| * |s2| ) ，如果假设他们的长度都为n，则复杂度为 O(n^2)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int _Min(int a,int b,int c)
{
int min=a;
if (b <min)
min=b;
if(c <min)
min=c;
return min;
}
int ComputeDistance(char s[],char t[])
{
int n = strlen(s);
int m = strlen(t);
//int d[][] = new int; // matrix
int **d = (int **)malloc((n+1) * sizeof(int *));
for(int i=0; i<=n; ++i)
{
d = (int *)malloc((m+1) * sizeof(int));
}
// Step 1
if (n == 0)
{
return m;
}
if (m == 0)
{
return n;
}
// Step 2
for (int i = 0; i <= n; i++)
{
d =i;
}
for (int j = 0; j <= m; d = j++)
{
d =j;
}
// Step 3
for (int i = 1; i <= n; i++)
{
//Step 4
for (int j = 1; j <= m; j++)
{
// Step 5
int cost = (t == s) ? 0 : 1;
// Step 6
d = _Min(d+1, d+1,d+cost);
}
}
// Step 7
return d;
}
int main(int argc, char *argv[])
{
char a;
char b;
printf("请输入字符串1\n");
scanf("%s",&a);
printf("请输入字符串2\n");
scanf("%s",&b);
int result= ComputeDistance(a,b);
printf("%d\n",result);
system("PAUSE");
return 0;
}
[ 本帖最后由 kon3155 于 2009-2-25 15:27 编辑 ]
【花瓶插花】
你想以最美观的方式布置花店的橱窗。你有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
【参考程序】//:============================“插花问题”的动态规划法算法============================
#define F 100
#define V 100
/**//*
插花问题描述:
将f束鲜花插入v个花瓶中,使达到最徍的视觉效果,
问题相关约定及插花要求:
鲜花被编号为1--f,花瓶被编号为1--v,花瓶按从小到
大顺序排列,一只花瓶只能插一支花,鲜花i插入花瓶j中的
视觉效果效果值已知,编号小的鲜花所放入的花瓶编号也小
问题求解思路:
花瓶j(1<=j<=v)中插入鲜花的可能编号为(编号
小的鲜花所放入的花瓶编号也小);
设数组p表示鲜花i插入花瓶j的好看程度,数组
q表示束鲜花插入个花瓶所能得到的最大
好看程度,初始化q = 0;q=0(1<=j<=v),则q
是问题的解.
特别地,j束鲜花插入到前面的j只花瓶中,所得到的好看
程度是q = p+p+...+.现将插花过
程按花瓶排列顺序划分成不同阶段,则在第j阶段,第i束鲜花
若放入第j号花瓶,最大好看程度是q+p;第i束鲜
花若放入前j-1个花瓶中的某一个,所得的好看程度是q,
那么在第j阶段,插入第i束鲜花所能得到的最大好看程度为:
q = MAX(q+p,q),要使q
最大,应使q和q也最大
*/
#define MAX(A,B) ((A) > (B) ? (A):(B)) //求取两数的最大值宏定义
#define F 100 //鲜花数最大值常量定义
#define V 100 //花瓶数最大值常量定义
//“插花问题”的初始化函数
// int f,v: 鲜花数量，花瓶个数
// int p[]: 鲜花i插入花瓶j的好看程度
void Flower_Initialize(int *f,int *v,int p[])
...{
int i,j;
printf("输入鲜花数量及花瓶个数:");
scanf("%d%d",f,v);
printf("顺序输入各鲜花插入各花瓶的好看程度: ");
for(i=1;i<=*f;i++)
for(j=1;j<=*v;j++)
p = i*j;
//scanf("%d",&p);
}
//“插花问题”的动态规划法解决函数
// int p[]: 鲜花i插入花瓶j的好看程度
// int f,v: 鲜花数量，花瓶个数
// int *way: 鲜花插入花瓶的插入方法结果
int Ikebana(int p[],int f,int v,int *way)
...{
int i,j,q,newv;
q = 0; //初始化[没有一束花插入花瓶时],好看程度自然为0
//设置v个花瓶分别被插入v束鲜花时各号花瓶对应的(初始)最大好看程度
for(j = 1;j <= v;j++)
...{
q = 0;
//设置第j束鲜花放入第j号花瓶中的最大好看程度
q = q + p;
}
for(j = 1;j <= v;j++)
for(i = 1;i < j;i++) //计算在第j阶段,插入第i束鲜花所能得到的最大好看程度
q = MAX(q + p,q);
newv = v;
for(i = f;i > 0;i--)
...{
while(q+p < q)
newv--;
//确定鲜花i插在花瓶newv中,并准备考虑前一只花瓶
way = newv--;
}
return(q);
}
//测试“插花问题”的动态规划法函数
void Run_Ikebana()
...{
//循环计数器，鲜花数量，花瓶个数，鲜花i插入花瓶j的好看程度，鲜花插入花瓶的插入方法结果
int i,f,v,p,way;
Flower_Initialize(&f,&v,p);
printf("最大好看程度点数为%d ",Ikebana(p,f,v,way));
printf("插有鲜花的花瓶是: ");
for(i = 1;i <= f;i++)
printf("%4d",way);
}
//:============================“插花问题”的动态规划法算法============================
int main(int argc, char* argv[])
...{
//Run_SubString();
Run_Ikebana();
printf(" 应用程序运行结束！ ");
return 0;
}
[ 本帖最后由 kon3155 于 2009-2-25 14:36 编辑 ]
【凸多边形三角划分】
给定一个具有N(N<50)个顶点(从l到N编号)的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小。
【输入格式】
第一行为顶点数N；
第二行为N个顶点(从1到N)的权值。
【输出格式】
最小的和的值。
【输入样例】
5
121 122 123 245 231
【输出样例】
12214884
【试题分析】
这是一道很典型的动态规划问题。设F（I<J）表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积，我们可以得到下面的动态转移方程：
F=Min{F+F+S*S*S} (I<K<J)
目标状态为：F
但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形甚至实形的范围，所以我们还需用高精度计算，但这是大家的基本功，程序中就没有写了，请读者自行完成。
【三】参考程序Var S :Array Of Integer;
F :Array Of Comp;
D :Array Of Byte;
N :Integer;
Procedure Init; (输入数据)
Var I :Integer;
Begin
Readln(N);
For I:=1 To N Do Read(S);
End;
Procedure Dynamic; （动态规划）
Var I,J,K :Integer;
Begin
For I:=1 To N Do
For J:=I+1 To N Do F:=Maxlongint; （赋初始值）
For I:=N-2 Downto 1 Do
For J:=I+2 To N Do
For K:=I+1 To J-1 Do
If (F>F+F+S*S*S) Then
Begin
F:=F+F+S*S*S;
D:=K; （记录父节点）
End;
End;
Procedure Print(I,J:Integer);（输出每个三角形）
Begin
If J=I+1 Then Exit;
Write(',',I,' ',J,' ',D);
Out(I,D);
Out(D,J);
End;
Procedure Out;（输出信息）
Begin
Assign(Output,'Output.Txt'); Rewrite(Output);
Writeln('The minimum is :',F:0:0);
Writeln('The formation of ',N-2,' triangle:');
Write(1,' ',N,' 'D);
Out(1,D);
Out(D,N);
Close(Output);
End;
Begin（主程序）
Init;
Dynamic;
Out;
End.
[ 本帖最后由 kon3155 于 2009-2-25 14:51 编辑 ]
【快餐店】
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个薯条的情况下最多可生产饮料的个数。
用r表示第I条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。
态转移方程 ： p = Max{p+r}
(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条生产线可以生产的套数，如果大于上限值则可以直接输出上限值并退出。否则再调用动态规划，而在动态规划求解的过程中，也可以在每完成一阶段工作便和上限值进行比较，若大于等于上限值就退出，这样一来，就可以尽早的求出解并结束程序。
具体的算法流程为：
http://www.piccdrop.com/images/1235545439.gif
【三】小结
动态规划虽然是种高效的算法，但不加优化的话，有可能在时间和空间上仍然有问题，因此，在做题时要充分发掘题目中的隐含条件，并充分利用已知条件，这样才能令程序更快，更优。
【四】对程序优化的进一步讨论:
本题在具体实现中还有一些优化的余地，在此提出，以供参考：
（1） 存储结构：由于每一阶段状态只与上一阶段状态有关，所以我们可以只用两个100*100的数组滚动实现。但考虑到滚动是有大量的赋值，可以改进为动态数组，每次交换时只需交换指针即可，这样比原来数组间赋值要快。
（2） 减少循环：在计算每一阶段状态过程中无疑要用到4重循环，其实这当中有很多是可以省掉的，我们可以这样修改每一重循环的起始值：
原起始值： 改进后的起始值：
for I := 1 to n do begin for I := 1 to n do begin
for j := 0 to tot div p1 do for j := 0 to min(q1,tot div p1) do
for k := 0 to (tot-p1*j) div p2 do for k := 0 to min(q2,(tot-p1*j) div p2) do
for j1:=0 to j do for j1 := max(0,j-t div p1) to
min(j,tot div p1) do
for k1 := 0 to k do for k1 := max(0,k-(t-(j-j1)*p1) div p2)
to min(k,(tot-p1*j1)div p2) do
{ 注：具体变量用途请参考程序 }
【五】参考程序{\$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
{\$M 65520,0,655360}
program FastFood;
const
input = 'input2.txt';
output = 'output2.txt';
var
f : text;
r,p,pp : array of integer; ｛pp:滚动数组中存放前一阶段的数组｝
t,tot,tt : array of longint;{tt:辅助数组；t:每条生产线的生产线时间；
tot:1-I条生产线生产时间的总和}
n,a,b,c,p1,p2,p3 : longint; {a,b,c:汉堡，薯条，饮料的个数；
p1,p2,p3汉堡，薯条，饮料的生产单位耗时}
procedure init;
var
i : integer;
begin
assign(f,input);
reset (f);
readln(f,a,b,c);
readlN(f,p1,p2,p3);
readln(f,n);
for i := 1 to n do read(f,t);
close (f);
if n=0 then begin{ 特殊情况处理 }
assign(f,output);
rewrite(f);
writeln(f,0);
close (f);
halt;
end;
end;
functionmin(i,j : longint) : longint; {求两数中较小的一个}
begin
if i>j then min := j else min := i;
end;
functionmax(i,j : longint) : longint; {求两数中较大的一个}
begin
if i>j then max := i else max := j;
end;
procedure main;
var
q,q1,q2,i,j,k,j1,k1 : longint;{q:上限值；q1,q2 : A,B的上限值}
begin
q := min( 100 div a,min( 100 div b, 100 div c ) ); {求上限值}
q1 := q*a;
q2 := q*b;
tt := t;
i := 1;
j := q1*p1;
while (j>0) and (i<=n) do { 用贪心法求出N条生产线可以生产的套数（可行解）}
if j>tt then begin
dec(j,tt);tt := 0; inc(i);
end
else begin dec(tt,j); j := 0; end;
if j=0 then begin
j := q2*p2;
while (j>0) and (i<=n) do
if j>tt then begin
dec(j,tt) ;tt := 0; inc(i);
end
else begin dec(tt,j); j := 0; end;
if j=0 then begin{如果可行，直接输出上限值}
assign(f,output);
rewrite(f);
writeln(f,q);
close (f);
halt;
end;
end;
tot := 0;
for i := 1 to n do tot := tot + t;
if tot div (a*p1+b*p2+c*p3)<q then begin{否则修改上限值}
q := tot div (a*p1+b*p2+c*p3);
q1 := q*a;
q2 := q*b;
end;
for i := 1 to n do begin
for j := 0 to min(q1,t div p1) do
for k := 0 to min(q2,(t-p1*j) div p2) do
r := (t-p1*j-p2*k) div p3;
fillchar(p,sizeof(p),0); {数组清零}
for j := 0 to min(q1,tot div p1) do
for k := 0 to min(q2,(tot-p1*j) div p2) do
for j1 := max(0,j-t div p1) to min(j,tot div p1) do
for k1 := max(0,k-(t-(j-j1)*p1) div p2) to min(k,(tot-p1*j1) div p2) do
if p < pp + r then
p := pp + r;
if p>=q*c then begin
{如果在此阶段产生了不小于上限值的解，则之际输出上限值，并直接退出}
assign(f,output);
rewrite(f);
writeln(f,q);
close (f);
halt;
end;
pp := p;
for j := 0 to min(100,tot div p1) do
for k := 0 to min(100,(tot-p1*j) div p2) do
if p > 100 then p := 100;
end;
{ out }
k1 := 0; { 输出最优值}
for j := 0 to 100 do
if (j div a > k1) then
for k := 0 to 100 do
if (k div b > k1) and (p div c > k1 ) then
k1 := min( min( j div a, k div b), p div c );
assign(f,output);
rewrite(f);
writeln(f,k1);
close (f);
end;
begin
init;
main;
end.
辛苦了