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