求最优平均分派算法 在线等待(300分)

请教各位一个算法问题
有N 个金额 : X1,X2,X3.....Xn
分派给M个人 : Y1,Y2.....Ym
M<<N
要球 M 个人得到的总金额尽量平均(在金额平均的基础上 还要求数量平均)
想了好久没有发现一个特别好的办法

各位仁兄好歹说几句啊

第一步:N 个金额相加/M 算出平均值.
第二步:每个金额与平均值比较, 大于平均值分配给一个人.
第三步: 剩余金额进行组合......

呵呵，问题就是怎么组合?
第三步: 剩余金额进行组合......

第三步: 剩余金额与剩余人重新进行第一、第二步计算，直到第二步中没有金额符合条件
第四步： 进行组合， 抱歉，没想好！

to yuzk2005
>>第二步:每个金额与平均值比较, 大于平均值分配给一个人
呵呵，兄弟，这里打错了吧 ，大于平均值分配给一个人 那其它 (m-1)个人怎么办？

例如金额为(50,20,10,5,2,1,0.5,0.2,0.1) 人数为4个
第一步:N/M 求出每个人要分配份数 (9/4 = 2,每人分配两份)
第二步:N%M 求出余下的金额份数 (9%4 = 1,剩余一份)
第三步:将最大的与最小的相加从新组成一份 (现在变成50.1,20.2,10.5,6,2)
重复第一和第二步 直到 N/M = 1(确定数量平均)
最后将N%M的份额数按大到小分配给第三步所得到的按小到大排列的结果

to zhuangqr
你这个有问题哟

什么问题啊? 未请教~!

你举的这个例子 最优的应该是
y1:50
y2:20
y3:10
y4:5+2+1+0.5+0.2+0.1
但按你自己算法 出来的肯定不是这个结果

－－－－－－－－－－
有N 个金额 : X1,X2,X3.....Xn
分派给M个人 : Y1,Y2.....Ym
－－－－－－－－－－－－－－－－－－
１。把你的金额排序，得到一个从大到少的序列。
２。从最大的金额开始，先给每个人先分一份。
３。从第m+1分开始，给得到金额总数最少的一份，直到分完。（你可以把人按得到金额的总数排序，得到一个小到大的序列，给排在第一位人分一份，分完一份后再进行排序，直到全部分完为止！）

同意qqjm

[]

to qqjm
上面chshanghai举的例子你就分不好了。我认为在第二次分时要考虑Xn与Xn-1之间的差额及余额之间的关系。

to chshanghai
你说的对,应该首先考虑金额平均.
那么 qqjm 提出来的是对的,不过需要补充的是当发现有金额相等的时候必须再考虑把下一份分给数量少的那个人

zhuangqr举的例：例如金额为(50,20,10,5,2,1,0.5,0.2,0.1) 人数为4个。
这个是比较极端的例子，这个例子标准差太大，我承认，我的上面的算法是不能做到数量平均的，所以用我的算法会得到以下结果：
首次：y1(50):50 y2(20):20 y3(10):10 y4(5):5
第二次：y1(50):50 y2(20):20 y3(10):10 y4(5,2):7
......：y1(50):50 y2(20):20 y3(10):10 y4(5,2,1):8
......：y1(50):50 y2(20):20 y3(10):10 y4(5,2,1,0.5):8.5
......：y1(50):50 y2(20):20 y3(10):10 y4(5,2,1,0.5,0.2):8.7
最后：y1(50):50 y2(20):20 y3(10):10 y4(5,2,1,0.5,0.2,0.1):8.9
如果各个金额都是比较平均的，我这个算法才能得到一个数量和金额都平均的的果。
数量平均和金额平均是对立的，想得到平衡，的话，可以给金额加一“权”上去！
如上面的例子，我给每个金额加一个10 的&quot;权&quot;。
(50,20,10,5,2,1,0.5,0.2,0.1)－》(60,30,20,15,12,11,10.5,10.2,10.1)
首次：y1(60):60 y2(30):30 y3(20):20 y4(15):15
。。。：y1(60):60 y2(30):30 y3(20):20 y4(15，12):27
。。。：y1(60):60 y2(30):30 y3(20，11):31 y4(15，12):27
。。。：y1(60):60 y2(30):30 y3(20，11):31 y4(15，12，10.5):37.5
。。。：y1(60):60 y2(30，10.2):40.2 y3(20，11):31 y4(15，12，10.5):37.5
。。。：y1(60):60 y2(30，10.2):40.2 y3(20，11，10.1):41.1 y4(15，12，10.5):37.5
最后结果是：y1(50):60 y2(20，0.2):40.2 y3(10，1，0.1):41.1 y4(5，2，0.5):37.5
这个是数量和金额都比较平均的结果，至于这个权怎么加，
你看你怎么控制了，权越大，数量越平均，权越小，金额越平均。如果权是接近于（总金额/分配人数），就可以得到金额平均和数量平均的平衡结果。
还权还有一种加法：就是每个第个金额设定一个独立的权，这个是人工做法了。。

不好意思：“如果权是接近于（总金额/分配人数），就可以得到金额平均和数量平均的平衡结果”是个人的猜策，没有数学依据，也没有实际计算过。
后来想了想，就应该是（总金额/金额总数）才对，但也是猜的，希望有数学高手验证一下。
呵呵。。。。。。。