a***n
发帖数: 3633 | 1 听说这里人气旺，求教个问题。
看到之前有人问三分数组的问题，我这个问题有些类似，不过不是要求一定三等分，而是
要求三分的尽量公平。
【 以下文字转载自 Programming 讨论区 】
发信人: addin (add+in), 信区: Programming
标 题: 请教算法： 三等分石子
发信站: BBS 未名空间站 (Sat Aug 17 21:49:31 2013, 美东)
请问一个算法问题，一堆石子，重量都是整数。把他们分成三堆，重量尽可能接近,
即重量最大的那堆和最小的那堆差值最小。请问这种问题怎么处理。如果扩展成分为n
堆呢？
我知道回溯肯定可以，动态规划行不行？
多谢。 | g**G
发帖数: 767 | 2 先从小到大排一下序，求和，然后从右往左扫？ 扫到超过总和的1/3 就开始扫下一堆 | g***9
发帖数: 159 | | z***y
发帖数: 50 | 4 3 79 80 159 160
从右往左, 得到的是 319 159 3 么?
【在 g**G 的大作中提到】
: 先从小到大排一下序，求和，然后从右往左扫？ 扫到超过总和的1/3 就开始扫下一堆
| z***y
发帖数: 50 | 5 把n粒石子放进k个箱子, 应该是从小到大排列, 然后从大的开始, 往重量最轻的箱子里
放. | e*******8
发帖数: 94 | 6 这题还是得用dp吧。要是greedy的话，k ＝ ２，输入是５，４，３，３，３呢？可以
把５和４放在一起，然后３，３，３放在一起，最大／最小差是０；但是greedy会把５
，３放一起，然后４，３，３一起，最大／最小差是２
【在 z***y 的大作中提到】
: 把n粒石子放进k个箱子, 应该是从小到大排列, 然后从大的开始, 往重量最轻的箱子里
: 放.
|
|
