 |
1
wy315700 Apr 7, 2015
每次把排好序的订单里 取出最小的，放到10个组里面和最小的那个里
|
|
2
wy315700 Apr 7, 2015
或者压根不需要对1000个订单进行排序，每次取出一个 放到10个组里面和最小的那个里
复杂度 1000 log(10) |
 |
3
dingyaguang117 Apr 7, 2015
我觉得LZ意思应该是在单数相等的情况下，总额尽量相等吧。不然连最优解的定义都不明确了
|
|
4
dingyaguang117 Apr 7, 2015
如果要求总额尽量相等， 单数这个应该可以忽略吧？
A: 1000*1 B： 20 *50 |
|
5
dingyaguang117 Apr 7, 2015
另外我真的很好奇LZ这个需求是什么情况下产生的，相当难想象
|
 |
6
9hills Apr 7, 2015
如果只是这个场景，你用NlogN绝对是足够了。没必要优化
|
|
7
dingyaguang117 Apr 7, 2015
@wy315700 不排序真的误差很大，我觉得应该排序完之后，按照从大到小的次序取出，放到当时最小的那个桶里， 因为是从大到小取出的，最后的偶然因素引起的突变会越来越小
|
 |
8
justfly Apr 7, 2015
排序 把排好顺序的订单先依次从1到10放进10个桶中 然后再从10到1 如此往复
|
 |
10
binux Apr 7, 2015
看你的描述，根本不是最优解啊，你是不需要最优解吗？
|
 |
11
zipher Apr 7, 2015
这方法不正确啊，999个100 和1个10000 按照你的方法应该不是你的预期把
另外 你这个描述很模糊“每组的单数和每组订单的总额尽量相等” |
 |
12
h4x3rotab Apr 7, 2015
虽然没仔细想，但是目测最优解是一个NPC问题，我觉得模拟退火用在这个问题上不错
|
 |
13
darrenxyli Apr 8, 2015
DP。m[i, j] = max{m[i-1, j], m[i-1, j-ai]}, j = total/10. 分10次DP，每次i=10就跳出，选中的剔除。
|
Select Language