看板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