最近做一个追费系统,目前碰到的主要的难点是最优分单的问题,
  有N个欠费的客户,每个客户对应一个自己欠费金额(fee[i];0<i<=N),现在要把这些欠费的客户分配到M个追费人员,
  问在保证 分到客户数最多的与最小的差不大于1个的情况下,怎么分配能使分到最多欠费金额的与最少金额的差最小,最小值是多少

解决方案 »

  1.   

    应该是npc问题吧.应该没有很好的算法.
      

  2.   

    这个比较的难,我想了个可以减小差额的方法
      
      fee[1..M]排序,假设为从高到低
      追款人为man[1..M],
      先将fee[1..N]中的fee[1..M]分配给man[1..M],
        若还有剩余,将剩余按反响的顺序分配给追款人,
      fee[M+1..2M]->man[M..1],如此循环,直至分培完。
      

  3.   

    to sqlink() ,穷举在数据大的情况下是不可能的,时间复杂度是指数增长的
      

  4.   

    fndxm(愤怒的小马) 的方法不错,不过我认为每分配完以后应该对每个追债人现在所追债物的总额按照从大到小进行排序,之后再将fee中的反向分配给追债人。鉴于每次分配以后之间总额的差距应该不大,整个数据大小分布比较均匀,因此推荐二分查找,速度应该比较快。不知道大家意思如何?