看板ACMCLUB
標 題Re: [問題] 分數字
發信站批踢踢兔 (Wed Jan 26 13:23:57 2005)
轉信站ptt!Group.NCTU!grouppost
※ 引述《[email protected] (小尹)》之銘言：
: ※ 引述《pangfeng (Ikari Gendou)》之銘言：
: : 將N個數字分P組, 要求P組的最大數字合為最小. 如何進行?
: : P=2時就是partition問題, 這類NPC問題不會有好的解.
: : 一個greedy的做法是將數字排序,
: : 再將數字由大到小指定到目前合為最小的組.
: : 實做出來P = 2 到 10 還OK, 但 P = 15, 16 時就很糟糕.
: : A good heuristic, anyone?
: 每組最大的數字 加起來 要最小嗎?
: 那把最小的 p-1 個數字分在 p-1 個組, 剩下其他的數字通通放同一組
抱歉中文不是寫的很清楚.
每一組數字算出合. 要求P個合中最大的合為最小的分組方法.
--
盡量平均分配的意思.
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 140.112.28.27