这是一个创建于 3550 天前的主题，其中的信息可能已经有所发展或是发生改变。
背景:
假设有1000个订单，每个订单的金额不同且相差较大，要分成10组来处理这些订单，希望每组的单数和每组订单的总额尽量相等，请问如何分配。希望各位给出算法设计和复杂度计算。
抛砖：
目前我的想法：先对1000个订单的金额进行排序，然后将拍好序的订单按照蛇形方式分配到10组内，即第1～10个订单分别分配到第1～10个组内，当11～20分别分配到第10~1个组内，如此重复。这样的时间复杂度是排序的复杂度O(n log_n)。
假设有1000个订单，每个订单的金额不同且相差较大，要分成10组来处理这些订单，希望每组的单数和每组订单的总额尽量相等，请问如何分配。希望各位给出算法设计和复杂度计算。
抛砖：
目前我的想法：先对1000个订单的金额进行排序，然后将拍好序的订单按照蛇形方式分配到10组内，即第1～10个订单分别分配到第1～10个组内，当11～20分别分配到第10~1个组内，如此重复。这样的时间复杂度是排序的复杂度O(n log_n)。
第 1 条附言 · 2015-04-08 09:56:25 +08:00
谢谢各位的回答，可能由于我的问题对于最优解的定义不是很清楚，该问题中每组的单数不一定是固定的，虽然固定后会简化问题，但得到的应该不是最优解。
重新定义下最优解，问题希望每组的单数和每组订单的总额尽量相等，可以将这个模糊的需求翻译成数学语言，最优解使每组订单数的方差加上每组订单总额的方差二者的和最小。
希望各位继续发言，谢！
重新定义下最优解，问题希望每组的单数和每组订单的总额尽量相等，可以将这个模糊的需求翻译成数学语言，最优解使每组订单数的方差加上每组订单总额的方差二者的和最小。
希望各位继续发言，谢！
 |
1
wy315700 2015-04-07 17:53:03 +08:00
每次把排好序的订单里 取出最小的，放到10个组里面和最小的那个里
|
|
2
wy315700 2015-04-07 17:53:56 +08:00
或者压根不需要对1000个订单进行排序，每次取出一个 放到10个组里面和最小的那个里
复杂度 1000 log(10) |
 |
3
dingyaguang117 2015-04-07 17:58:41 +08:00
我觉得LZ意思应该是在单数相等的情况下，总额尽量相等吧。不然连最优解的定义都不明确了
|
|
4
dingyaguang117 2015-04-07 18:00:20 +08:00
如果要求总额尽量相等， 单数这个应该可以忽略吧？
A: 1000*1 B： 20 *50 |
|
5
dingyaguang117 2015-04-07 18:00:57 +08:00
另外我真的很好奇LZ这个需求是什么情况下产生的，相当难想象
|
 |
6
9hills 2015-04-07 18:03:01 +08:00
如果只是这个场景，你用NlogN绝对是足够了。没必要优化
|
|
7
dingyaguang117 2015-04-07 18:03:28 +08:00
@wy315700 不排序真的误差很大，我觉得应该排序完之后，按照从大到小的次序取出，放到当时最小的那个桶里， 因为是从大到小取出的，最后的偶然因素引起的突变会越来越小
|
 |
8
justfly 2015-04-07 18:21:49 +08:00
排序 把排好顺序的订单先依次从1到10放进10个桶中 然后再从10到1 如此往复
|
 |
10
binux 2015-04-07 18:26:19 +08:00
看你的描述，根本不是最优解啊，你是不需要最优解吗？
|
 |
11
zipher 2015-04-07 19:26:32 +08:00
这方法不正确啊，999个100 和1个10000 按照你的方法应该不是你的预期把
另外 你这个描述很模糊“每组的单数和每组订单的总额尽量相等” |
 |
12
h4x3rotab 2015-04-07 19:54:15 +08:00
虽然没仔细想，但是目测最优解是一个NPC问题，我觉得模拟退火用在这个问题上不错
|
 |
13
darrenxyli 2015-04-08 06:13:02 +08:00
DP。m[i, j] = max{m[i-1, j], m[i-1, j-ai]}, j = total/10. 分10次DP，每次i=10就跳出，选中的剔除。
|
Select Language