看板ACMCLUB
标 题Re: [问题] 分数字
发信站批踢踢兔 (Thu Jan 27 04:32:14 2005)
转信站ptt!Group.NCTU!grouppost
※ 引述《pangfeng (Liu)》之铭言：
: 将N个数字分P组, 要求P组的最大数字合为最小. 如何进行?
: P=2时就是partition问题, 这类NPC问题不会有好的解.
: 一个greedy的做法是将数字排序,
: 再将数字由大到小指定到目前合为最小的组.
: 实做出来P = 2 到 10 还OK, 但 P = 15, 16 时就很糟糕.
: A good heuristic, anyone?
我以simulated annealing进行
在N/P值为5以上时均大部分能达到最小群/最大群 > 0.88
(收敛系数0.98)
只是随机过程需要时间甚长
我是以随机选一些数子来换群组的方法
在N=1000左右时就很慢而不切实际了(about 10min)
如果有更好的随机化方法那此法应该可行
--
※ 发信站: 批踢踢兔(ptt2.cc)
◆ From: 140.112.248.177