花束制作实验报告.doc

篇一：花束摆放实验报告
算法设计与分析实验报告
动态规划之花束摆放问题
一.　问题描述
现有f束不同品种的花束（每束花用1~ｆ的整数唯一标识)和　至少为同样数量的花瓶按顺序摆成一行，其位置固定于架子上并按从1到v从左到右依次摆放。其中v为花瓶的数量，则有f＆lt;=ｖ。标识花束的整数决定了花束在花瓶中的顺序。例如有花束ｉ和花束（ｊｉ＆lt;ｊ),若花瓶的个数多于花束的数量，则多出来的花瓶空置。
假设每个花瓶都具有各自的特点，那么当不同的花束放入不同的花瓶的
时候便会产生不同的美学效果，并用一个美学值来（整数）表示。约定空置的花瓶的美学值为０。为取得最大的美学效果，必须在保持花束的顺序的前提下,使花束的摆放取得最大的美学值。现需给出一种取得最大美学值的摆放方式。
二． 求解思路
设b【ｉ】【ｊ】表示第i朵花放在第ｊ个瓶子里产生的美学值,
设m【i】【j】表示总共i朵花放入j个瓶子中产生的最大美学值(其中i＆ｌt；=j）
思路一：采用分治法的思想,当花束数量等于花瓶数量，即f＝v 时，问题只有一种解决方案。那么，当f&lｔ；v时,求解f朵花放入v个瓶子的最大美学值可以转化为求解f—1朵花放入k（f—2＆lｔ；k<j）个瓶子的最大美学值加上第ｆ朵花放在第v个瓶子所产生的美学值.　即:ｍ［i］［ｊ] =　ｍax{m［f—１][k]（ｆ-2＆lt；k＆lt;ｊ)｝+ｂ［i］［j];但上述思路是有缺陷的，因为以上思路是假设第f朵花放在了第ｖ个瓶子中,
而实际情况下,求解f朵花束放入v个瓶子中的最大美学值时第i朵花束并不一定放在第v个瓶子中(当ｖ＆gt;f时,根据鸽舍原理，一定有一朵花有至少两种选择放入不同的花瓶中。假设这就是第f朵花，则它不一定放入第v个瓶子中）.假如第f朵花不是放在第ｖ个瓶子中而是在选出的方案中选择一个空置的瓶子放入，则可能破坏了花束的摆放顺序，不符合题意。那么要求得f朵花放入v个花瓶中的最大美学值,就必须遍历所有花束摆放的情形,找出其最大值， 也就是ｍ［f］[v]=mａx｛m[f］[f］，m[f][f+1]，……，ｍ[f]［v］｝;
而且在每一次将问题细分的时候，需要找到前面所取得的最大美学值,这一
过程实际上是有重复的。比如下面这个例子：
1２34　求2朵花放在4个瓶子里产生的最大美学　1834９ 实际上和2朵花放在3个瓶子里产生的最大　２ 3712 美学值相同。若采用上述的方法,需要比较 3　 15２5 两次２朵花放在３个瓶子里的情况。
思路二：上述方法尽管有缺陷，但我们可以基于以上思想进行改进。我们用
m[i][j］表示ｉ朵花放入j个花瓶中产生的最大美学值。那么当第i朵花放在第ｊ个瓶子时，我们只需知道前i-1个瓶子放入j－１个瓶子的最大美学值m[i—1］［j-１］,也就m［i]［j］＝m［ｉ-１]［ｊ－1］＋ｂ［i］［ｊ］;
若第i朵花不放在第ｊ个瓶子中，则问题变为求解i朵花放入前j—１个瓶子的最大美学值,也就是m[i］［j]＝ｍ［i]［j—１];这两种情况可以囊括所有ｉ朵花束放入ｊ个花瓶中的情形，且对于每个m［i]［j]来说，求解它的值可以化为求解它的子问题m[ｉ—1］［j—１］或m[i］［j—１],不会出现重复计算。
因此,计算