这是一个创建于 3906 天前的主题，其中的信息可能已经有所发展或是发生改变。
背景:
假设有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