花束摆放实验报告.docx

算法设计与分析试验报告

动态规划之花束摆放问题

一． 问题描述

现有f束不同品种的花束〔每束花用1～f的整数唯一标识〕和

至少为同样数量的花瓶按挨次摆成一行，其位置固定于架子上并按从1到v从左到右依次摆放。其中v为花瓶的数量，则有f=v。标识花束的整数打算了花束在花瓶中的挨次。例如有花束i和花束〔jij〕则花束j不能放在花束i的前面。每个花瓶只能放一种花束，假设花瓶的个数多于花束的数量，则多出来的花瓶空置。

假设每个花瓶都具有各自的特点，那么当不同的花束放入不同的花瓶的时候便会产生不同的美学效果，并用一个美学值来〔整数〕表示。商定空置的花瓶的美学值为0。为取得最大的美学效果，必需在保持花束的挨次的前提下，使花束的摆放取得最大的美学值。现需给出一种取得最大美学值的摆放方式。

二． 求解思路

设B【i】【j】表示第i朵花放在第j个瓶子里产生的美学值，

设M【i】【j】表示总共i朵花放入j个瓶子中产生的最大美学值〔其中i=j〕

思路一：承受分治法的思想，当花束数量等于花瓶数量，即f=v

时，问题只有一种解决方案。那么，当fv时，求解f朵花放入v个瓶子的最大美学值可以转化为求解f-1朵花放入k〔f-2kj〕个瓶子的最大美学值加上第f朵花放在第v个瓶子所产生的美学值。

即：M[i][j]=max{M[f-1][k](f-2kj)}+B[i][j];

但上述思路是有缺陷的，由于以上思路是假设第f朵花放在了第v个瓶子中，而实际状况下，求解f朵花束放入v个瓶子中的最大美学值时第i朵花束并不肯定放在第v个瓶子中〔当vf时，依据鸽舍原理，肯定有一朵花有至少两种选择放入不同的花瓶中。假设这就是第f朵花，则它不肯定放入第v个瓶子中〕。假设第f朵花不是放在第v个瓶子中而是在选出的方案中选择一个空置的瓶子放入，则可能破坏了花束的摆放挨次，不符合题意。那么要求得f朵花放入v个花瓶中的最大美学值，就必需遍历全部花束摆放的情形，找出其最大值，

也就是M[f][v]=max{M[f][f],M[f][f+1],……,M[f][v]};

而且在每一次将问题细分的时候，需要找到前面所取得的最大美学值，这一过程实际上是有重复的。比方下面这个例子：

1

2

3

4

求2朵花放在4个瓶子里产生的最大美学

18

3

4

9

实际上和2朵花放在3个瓶子里产生的最大

2 3

7

1

2

美学值一样。假设承受上述的方法，需要比较

3 1

5

2

5

两次2朵花放在3个瓶子里的状况。

思路二：上述方法尽管有缺陷，但我们可以基于以上思想进展改进。我们用M[i][j]表示i朵花放入j个花瓶中产生的最大美学值。那么当第i朵花放在第j个瓶子时，我们只需知道前i-1个瓶子放入j-1个瓶子的最大美学值M[i-1][j-1],也就M[i][j]=M[i-1][j-1]+B[i][j];

假设第i朵花不放在第j个瓶子中，则问题变为求解i朵花放入前j-1个瓶子的最大美学值，也就是M[i][j]=M[i][j-1];这两种状况可以囊括全部i朵花束放入j个花

瓶中的情形，且对于每个M[i][j]来说，求解它的值可以化为求解它的子问题M[i-1][j-1]或M[i][j-1],不会消灭重复计算。

因此，计算M[i][j]具有求解最优子构造的性质。其计算方式为：M[i][j]=max{M[i][j-1],(M[i-1][j-1]+B[i][j])} 。值得留意的是，当i=1时，

M[1][j]=max{M[1][j-1],B[1][j]}.

我们可以用一个例子来说明这个算法：

为了保持花束的挨次，我们可以规定第i朵花只能放在第i~v-f+1个瓶子上，也就是当ji或者当jv-f+1时B[i][j]=0。据此，我们给出一组3朵花放在5个瓶子里的美学值：

花\瓶

1

2

3

4

1

6

10

0

0

2

0

4

7

0

3

0

0

6

3

那么依据上述的求解最优子构造的动态规划算法，可以得到下面这个二维数组

M[i][j]:

花\瓶

1

2

3

4

1

6(B[1][1])

10(B[1][2])

10(M[1][2])

10(M[1][3])

2

0

10(M[1][2]+

B[2][2])

17(M[1][2]+

B[2][3])

17(M[2][3])

3

0

0

16(M[2][2]+

B[3][3])

20(M[2][3]+

B[3][3])

三.具体实现:

试验环境：Dev-C++

试验数据：本试验给出20组数据作为数据集写入data.txt中