数组拆分算法

liangbch

定义： 数组的跨度：如一个数组中最小的那个数是x。则这个数组的跨度L=n-x+1，注意n并非这个数组中最大的那个数，而是所有数组中最大的数。 令tl为跨度和，定义加速比：s=(n+1)*n/2 /tl 对于我的应用,加速比是最重要的一个指标，加速比越大越好，加速比相同的情况下，拆出来的数组的越小越好。 三种算法实验结果；

N	算法	数组个数	加速比
100	Lbc 算法一	6	16.503268
	Lbc 算法二	5	16.237942
	Gxq 改进算法	6	11.85
1024	Lbc 算法一	104	10.555746
	Lbc 算法二	72	11.848908
	Gxq 改进算法	86	8.362281

综上所述，算法2得到的结果是目前最好的。

gxqcn

老兄的评判标准是第一优先级为加速比越大越好，第二优先级才是分组组数越少越好。（怎不早说啊？ ） 就第一点来说，加速比实则仅与分组后各数组的最小数之和相关， 所以应尽量将小数字相对集中。 感觉 Lbc 算法二已经比较优化了， 但不排除可以将结果人工局部调整，以提高进一步加速比的可能。

liangbch

言之有理，仔细看了下算法2的运行结果，应该可以进一步调整/优化。不过人工调整比较麻烦，目前正考虑如何调整算法。等新的算法出来后，我将给出代码和运行结果。

liangbch

想了好久，一直没有找到令自己满意的算法，目前总算找到一个比较满意的，算法复杂度也较低。但还没有动手写程序，当然采用这个算法的程序也是最复杂的。

liangbch

这个问题题确实很复杂，现在的方案都是找到一个相对好的解，要找到最优解或者更优解确实很难。 仍在思考中......

gxqcn

这类问题找到最优解本身就有很大难度，好比成绩从98提到99一样。 一般出于应用，优化解基本可以达到目的，最优解可再提高的程度比较有限。 不过，对你的新算法还是非常期待的。。。

medie2005

设要将1到n这n个数分组. 将n!写成素数相乘的形式, $n!$$=p_{1}^{c_{1}}*...p_{k}^{c_{k}}$。 对$p_{1},p_{2},...,p_{k}$取以2为底的对数. 得到一个序列LOG[]: $log_{2}{p_{1}},...,log_{2}{p_{1}},log_{2}{p_{2}},...,log_{2}{p_{2}},...,log_{2}{p_{k}}$. 对LOG[]中的数从大往小取数,放进大小为32的背包.对已经放东西的背包,维持这些背包按剩余空间的大小降序排列. 假设当前处理到LOG[ i ]. i)、如果已经放东西的背包序列中的第一个包的剩余空间大于LOG[ i ],则把LOG[ i ]放入,并且按剩余空间的大小,调整已经有东西的背包的顺序. ii)、如果不是,则把LOG[ i ]放入新的背包,并且按剩余空间的大小,调整已经有东西的背包的顺序.

无心人

media2005你测试下你的想法吧 这个题目他们除了两个 还没别人参与过呢

liangbch

27# 的做法能够保证每个数组的最小公倍数尽可能大，却不能保证数组尽可能少。

liangbch

$3491888400=16xx27xx25xx7xx9xx11xx13xx17xx19$ $3087564480=49xx64xx81xx5xx11xx13xx17$ $3171168000=121xx125xx128xx9xx7xx13xx2$ 49*64*81*121*125 = 3841992000 49*64*81*121*5*23 = 3534632640 49*64*23*29*31*5*9 = 2917938240 32*49*23*29*31*37*3= 3598790496 2 3 4 5 7 8 9 11 13 16 17 19 23 25 27 29 31 32 37 41 43 47 49 53 59 61 64 67 71 73 79 81 83 89 97 [ 本帖最后由 liangbch 于 2009-2-4 15:03 编辑 ]