数组拆分算法

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 编辑 ]