V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
xiaochong
V2EX  ›  问与答

实际应用中遇到的算法问题,请教各位大牛。

  •  
  •   xiaochong · 2015-04-07 17:21:32 +08:00 · 2290 次点击
    这是一个创建于 2740 天前的主题,其中的信息可能已经有所发展或是发生改变。
    背景:

    假设有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
    谢谢各位的回答,可能由于我的问题对于最优解的定义不是很清楚,该问题中每组的单数不一定是固定的,虽然固定后会简化问题,但得到的应该不是最优解。

    重新定义下最优解,问题希望每组的单数和每组订单的总额尽量相等,可以将这个模糊的需求翻译成数学语言,最优解使每组订单数的方差加上每组订单总额的方差二者的和最小。

    希望各位继续发言,谢!
    13 条回复    2015-04-08 06:13:02 +08:00
    wy315700
        1
    wy315700  
       2015-04-07 17:53:03 +08:00
    每次把排好序的订单里 取出最小的,放到10个组里面和最小的那个里
    wy315700
        2
    wy315700  
       2015-04-07 17:53:56 +08:00
    或者压根不需要对1000个订单进行排序,每次取出一个 放到10个组里面和最小的那个里

    复杂度 1000 log(10)
    dingyaguang117
        3
    dingyaguang117  
       2015-04-07 17:58:41 +08:00
    我觉得LZ意思应该是在单数相等的情况下,总额尽量相等吧。不然连最优解的定义都不明确了
    dingyaguang117
        4
    dingyaguang117  
       2015-04-07 18:00:20 +08:00
    如果要求总额尽量相等, 单数这个应该可以忽略吧?

    A: 1000*1
    B: 20 *50
    dingyaguang117
        5
    dingyaguang117  
       2015-04-07 18:00:57 +08:00
    另外我真的很好奇LZ这个需求是什么情况下产生的,相当难想象
    9hills
        6
    9hills  
       2015-04-07 18:03:01 +08:00
    如果只是这个场景,你用NlogN绝对是足够了。没必要优化
    dingyaguang117
        7
    dingyaguang117  
       2015-04-07 18:03:28 +08:00
    @wy315700 不排序真的误差很大,我觉得应该排序完之后,按照从大到小的次序取出,放到当时最小的那个桶里, 因为是从大到小取出的,最后的偶然因素引起的突变会越来越小
    justfly
        8
    justfly  
       2015-04-07 18:21:49 +08:00
    排序 把排好顺序的订单先依次从1到10放进10个桶中 然后再从10到1 如此往复
    lvfujun
        9
    lvfujun  
       2015-04-07 18:23:52 +08:00
    @justfly 牛逼!
    binux
        10
    binux  
       2015-04-07 18:26:19 +08:00
    看你的描述,根本不是最优解啊,你是不需要最优解吗?
    zipher
        11
    zipher  
       2015-04-07 19:26:32 +08:00
    这方法不正确啊,999个100 和1个10000 按照你的方法应该不是你的预期把
    另外 你这个描述很模糊“每组的单数和每组订单的总额尽量相等”
    h4x3rotab
        12
    h4x3rotab  
       2015-04-07 19:54:15 +08:00
    虽然没仔细想,但是目测最优解是一个NPC问题,我觉得模拟退火用在这个问题上不错
    darrenxyli
        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就跳出,选中的剔除。
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2184 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 37ms · UTC 15:36 · PVG 23:36 · LAX 08:36 · JFK 11:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.