近似平均分配问题

Question

现在有一批数据记录多笔【百万】贷款逾期的记录，分配给多个客服人员去拨打电话催缴，要求每个客服人员分到的笔数和催缴的总金额基本相差不大，例如，有5个客服，100笔逾期贷款，100笔逾期贷款的总金额是100W，那么每个客服分配到应该是20笔，20W总金额

Answer 1

这是个0-1规划问题或者0-1背包问题。有现成的动态规划算法，只要确定是倾向于数量更均衡还是金额更均衡。 min(sum(alpha * (abs(V_i - V_avg)) + beta * (abs(N_i - N_avg)))) s.t. sum(V_i) = V sum(N_i) = N 1 = alpha + beta alpha是金额差距的权重 beta是数量差距的权重

Answer 2

比如客服人数=3，贷款笔数=7，总欠款=10万。可先确定每人分得多少笔欠款（2,2,3），再以尽量接近平均欠款（3.33万）的额度分配贷款。具体方法可参考这个问题（重复线性规划）。 还有一个比较粗略的算法，实际应用比较方便：把贷款按金额从大到小的顺序，依次分配给累计分得金额最少的客服（相等则任选一个）。