《花束摆放实验报告》由会员分享，可在线阅读，更多相关《花束摆放实验报告（7页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析实验报告 动态规划之花束摆放问题一 问题描述现有f束不同品种的花束（每束花用1f的整数唯一标识）和至少为同样数量的花瓶按顺序摆成一行，其位置固定于架子上并按从1到v从左到右依次摆放。其中v为花瓶的数量，则有f=v。标识花束的整数决定了花束在花瓶中的顺序。例如有花束i和花束j（ij）则花束j不能放在花束i的前面。每个花瓶只能放一种花束，若花瓶的个数多于花束的数量，则多出来的花瓶空置。假设每个花瓶都具有各自的特点，那么当不同的花束放入不同的花瓶的时候便会产生不同的美学效果，并用一个美学值来（整数）表示。约定空置的花瓶的美学值为0。为取得最大的美学效果，必须在保持花束的顺序的前提下，使
2、花束的摆放取得最大的美学值。现需给出一种取得最大美学值的摆放方式。二 求解思路设B【i】【j】表示第i朵花放在第j个瓶子里产生的美学值，设M【i】【j】表示总共i朵花放入j个瓶子中产生的最大美学值（其中i=j）思路一：采用分治法的思想，当花束数量等于花瓶数量，即f=v时，问题只有一种解决方案。那么，当fv时，求解f朵花放入v个瓶子的最大美学值可以转化为求解f-1朵花放入k（f-2kj）个瓶子的最大美学值加上第f朵花放在第v个瓶子所产生的美学值。即：Mij = maxMf-1k(f-2kf时，根据鸽舍原理，一定有一朵花有至少两种选择放入不同的花瓶中。假设这就是第f朵花，则它不一定放入第v个瓶子中
3、）。假如第f朵花不是放在第v个瓶子中而是在选出的方案中选择一个空置的瓶子放入，则可能破坏了花束的摆放顺序，不符合题意。那么要求得f朵花放入v个花瓶中的最大美学值，就必须遍历所有花束摆放的情形，找出其最大值，也就是Mfv=maxMff,Mff+1,Mfv; 而且在每一次将问题细分的时候，需要找到前面所取得的最大美学值，这一过程实际上是有重复的。比如下面这个例子： 1 2 3 4 求2朵花放在4个瓶子里产生的最大美学1 8 3 4 9 实际上和2朵花放在3个瓶子里产生的最大2 3 7 1 2 美学值相同。若采用上述的方法，需要比较3 1 5 2 5 两次2朵花放在3个瓶子里的情况。思路二：上述方法
4、尽管有缺陷，但我们可以基于以上思想进行改进。我们用Mij表示i朵花放入j个花瓶中产生的最大美学值。那么当第i朵花放在第j个瓶子时，我们只需知道前i-1个瓶子放入j-1个瓶子的最大美学值Mi-1j-1,也就Mij=Mi-1j-1+Bij;若第i朵花不放在第j个瓶子中，则问题变为求解i朵花放入前j-1个瓶子的最大美学值，也就是Mij=Mij-1;这两种情况可以囊括所有i朵花束放入j个花瓶中的情形，且对于每个Mij来说，求解它的值可以化为求解它的子问题Mi-1j-1或Mij-1,不会出现重复计算。因此，计算Mij具有求解最优子结构的性质。其计算方式为：Mij = maxMij-1,(Mi-1j-1+
5、Bij)。值得注意的是，当i=1时，M1j=maxM1j-1,B1j.我们可以用一个例子来说明这个算法： 为了保持花束的顺序，我们可以规定第i朵花只能放在第iv-f+1个瓶子上，也就是当jv-f+1时Bij=0。据此，我们给出一组3朵花放在5个瓶子里的美学值：花瓶12341610002047030063那么根据上述的求解最优子结构的动态规划算法，可以得到下面这个二维数组Mij:花瓶123416(B11)10(B12)10(M12)10(M13)2010(M12+B22)17(M12+B23)17(M23)30016(M22+B33)20(M23+B33)三.具体实现: 实验环境：Dev-C+
6、实验数据：本实验给出20组数据作为数据集写入data.txt中。第i朵花放在第j个瓶子产生的美值Bij由随机数给出(当jv-f+1时，Bij=0)，其中10组数据1=f=v=10,另外10组数组1=f=v=100. 也可以自己手动输入花束数量f和花瓶数量v来查看实验结果。 实验测试：本实验通过data.txt文件读入20组数据，分别对其求解，并将所求得的结果写入result.txt文件中。对每次实验，Mfv就是最终所需要求得的最大美学值，我们可以利用一个数组method来存储所得到的摆放方案，即第i朵花放在第methodi个瓶子中，然后将method方案打印出来：对打印的方案method数组要
7、进行验证，保证花束的摆放顺序（即小号的花束不能放在大号的花束的右边）。也可以通过递归的方式将得到的最佳方案打印出来： 四结果分析 与分治法相比，动态规划有着明显的优势。对于本实验而言，若使用分治法，每次都要暴力枚举所有摆放情况才能得出最大美学值，因而算法的时间复杂度为O(n3)；而使用动态规划的话，由于问题的求解具有最优子结构的性质，当前问题的结果必定包含其子问题的结果，那么记录下每一个子问题的结果，采用自底向上的方法就可以较快捷地得出当前问题的结果。对于本实验而言，只需要两重循环，就能找出i朵花放入j个瓶子中的最大美学值，算法复杂度为O(n2). 使用动态规划求解问题的时候最重要的步骤就是找出当前问题与其子结构的联系。（Mij = maxMij-1,(Mi-1j-1+Bij)。）写出了这样的关系式，问题就容易解决了。
