小竹

现将一万个客户由大到小排序，设为K1，K2，……，K10000。
对于第一个员工，从K1开始，如果K1+K2小于35000万，则继续加，依次类推K1+K2+K3+……，直到有一个i使得K1+K2+……+Ki大于35000万，则抛掉Ki换Ki+1试试，若仍大于35000万，则抛掉Ki+1并换Ki+2试……直至得到35000万或所有客户都遍历，此时就得到一个近似解。
对于第二个员工则要把第一个员工手中的客户去掉然后再重复第一个员工的过程。
……
按上述算法，当第20个员工分配完后，会剩下一些客户（不过这些客户的量都较小，量大已经被选走），那就按“最小加最大”的原则再分配。如此就可以得到近似解。

youxi01

楼上的方式还是不太合理
原来有人提出思路:先排序,然后加一个最大的，再加个最小的，这种方式比较合理,更容易求出近似解...

小竹

我不认为那种算法有更好的优越性。
首先，都不能求出全局最优解，仅仅是局部的近似解。
其次，时间复杂度基本上是同一数量级。

随风

先说个思路看行不行
首先把这一万个客户倒排序,把7000个大的写入a.txt  把3000个小的写入b.txt
再把a.txt的第一个和最后一个相加,如果小于35000万,就再加第二个和倒数第二个,如果大于3500万,
就加b.txt的倒数第一个,依此类推....

youxi01

本来的思路就是这样的...

dishuo

思路：读取数据，排序，由大到小开始分配给员工，员工的查找顺序为1-2-3-…-20-20-19-…-2-1-1-2-…如此循环，如果当前员工的配额已经超过了平均最大购买量（=总购买量/员工数+总购买量mod员工数），则寻找下一个没超过的员工（可以证明一定存在）。

测试的时候用1000组数据即可看到效果，10000组的话......太慢了。

cls&@echo off&setlocal enabledelayedexpansion
if not exist list.txt call :creatlist
cls
set _bs=
set "_sp=                                                                        "
set/a 员工数=20
set/a 客户总数=0
set/a 总购买量=0
echo 当前问题:
echo     将 n个客户 分配给 20个员工 ,要求每个员工所分客户的总购买量大致相同.
echo.
echo.
for /f "tokens=2 delims= " %%i in (list.txt) do (
    set/a 客户总数+=1
    set/a 客户[!客户总数!]=客户总数
    set/a 客户购买量[!客户总数!]=%%i
    set/a 总购买量+=%%i
    set/p info=%_bs%正在导入数据,请稍等...[!客户总数!]<nul
)
set/p info=%_bs%%_sp%%_bs%<nul
echo 导入完毕.&echo.

set/a 平均最小购买量=总购买量/员工数
set/a 平均最大购买量=平均最小购买量+总购买量%%员工数
echo =====数据信息=====
echo       客户总数: %客户总数%
echo       总购买量: %总购买量%
echo 平均最小购买量: %平均最小购买量%
echo 平均最大购买量: %平均最大购买量%
echo.

call :QuickSort 1 %客户总数%
set/p info=%_bs%%_sp%%_bs%<nul
echo 排序完毕.&echo.

call :calculate
set/p info=%_bs%%_sp%%_bs%<nul
echo 分配完毕.&echo.

set/p info=完成! 按任意键显示员工任务表...<nul&pause>nul
set/p info=%_bs%%_sp%%_bs%<nul
echo =====员工任务表=====
for /l %%i in (1,1,%员工数%) do (
    echo 员工号:%%i 任务量:!员工任务量[%%i]! 额度:!员工额度[%%i]!
    echo !员工任务[%%i]!&echo.
)
pause
goto:eof

:calculate
for /l %%i in (1,1,%员工数%) do set "员工任务[%%i]="& set "员工任务量[%%i]=0"& set "员工额度[%%i]=0"
set/a 当前员工=0
set/a add=1
set/a count=0
for /l %%i in (%客户总数%,-1,1) do (
    set/a count+=1
    set/p info=%_bs%正在分配员工任务,请稍等...[!count!/%客户总数%]<nul
    set/a i=%%i
    :nextone
    set/a 当前员工+=!add!
    if !当前员工! gtr %员工数% set/a add=-1,当前员工=员工数
    if !当前员工! lss 1 set/a add=1,当前员工=1
    call set/a 测试额度=%%员工额度[!当前员工!]%%
    if !测试额度! leq %平均最大购买量% (
        call call set/a 员工额度[!当前员工!]+=%%%%客户购买量[%%客户[!i!]%%]%%%%
    ) else (
        goto nextone
    )
    call set 员工任务[!当前员工!]=%%员工任务[!当前员工!]%%!客户[%%i]!;
    set/a 员工任务量[!当前员工!]+=1
)
goto :eof

::use call :quicksort low high
:QuickSort
set/a dep=0
:QS
set/p info=%_bs%正在排序数据,请稍等...[%1/%客户总数%]<nul
set/a dep+=1,lTmpLow=%1,lTmpHi=%2,Low=%1,Hi=%2
if %Hi% leq %Low% set/a dep-=1&goto :eof
set/a lTmpMid=(Low+Hi)/2
call call set/a vTempVal=%%%%客户购买量[%%客户[!lTmpMid!]%%]%%%%
:qsMainLoop
if !lTmpLow! leq !lTmpHi! (
    :qsLoop1
    call call set/a vVal=%%%%客户购买量[%%客户[!lTmpLow!]%%]%%%%
    if !vVal! lss !vTempVal! if !lTmpLow! lss !Hi! set/a lTmpLow+=1& goto qsLoop1
    :qsLoop2
    call call set/a vVal=%%%%客户购买量[%%客户[!lTmpHi!]%%]%%%%
    if !vTempVal! lss !vVal! if !Low! lss !lTmpHi! set/a lTmpHi-=1&goto qsLoop2
    :qsSwap
    if !lTmpLow! leq !lTmpHi! (
        call set/a vTmpHold=%%客户[!lTmpLow!]%%
        call set/a 客户[!lTmpLow!]=%%客户[!lTmpHi!]%%
        set/a 客户[!lTmpHi!]=vTmpHold
        set/a lTmpLow+=1,lTmpHi-=1
    )
goto qsMainLoop
)
set/a lTmpLow[%dep%]=lTmpLow,Hi[%dep%]=Hi
if %Low% lss %lTmpHi% call :QS %Low% %lTmpHi%
call set lTmpLow=%%lTmpLow[!dep!]%%&call set Hi=%%Hi[!dep!]%%
if %lTmpLow% lss %Hi% call :QS %lTmpLow% %Hi%
set/a dep-=1&goto :eof

:creatlist
set /p length=创建多少个随机客户?
FOR /L %%i IN (1,1,%length%) DO echo %%i号客户 !random!>>list.txt
goto :eof

simplemen

楼上可以告诉我，你用的什么编辑器么，一直想找个这种有语法高亮，最好是有关键字提示的编辑器，可是别的语言都有，唯独批处理没有，

lolo

都用上Excel了，为什么不用VBA呢？

Sub allocate2() '假设数据区域从大到小排序
Dim employee(19), m(19)
For i = 0 To 19
Set employee(i) = CreateObject("Scripting.Dictionary")
Next i
Set lost = CreateObject("Scripting.Dictionary")
NUM = Application.InputBox("请输入客户数：", "选择运算范围", 580, , , , , 9)
If NUM < 20 Then MsgBox "请重新选择", , "选择有误!"
avg = Application.WorksheetFunction.Sum(Range("b1:b" & NUM)) / 20
guest = Range("a1:b" & NUM)
i = -1
For n = 1 To NUM
flag = False
t = 1
Do While t <= 20
i = (i + 1) Mod 20
If m(i) + guest(n, 2) <= avg Then
m(i) = m(i) + guest(n, 2)
employee(i).Add guest(n, 1), guest(n, 2)
flag = True
Exit Do
End If
t = t + 1
Loop
If flag = False Then
lost.Add guest(n, 1), guest(n, 2)
End If
Next n
End SubCOPY

lolo

说明：
    程序运行结束，employee(i) 保存的是每个员工分得的客户情况，lost 则保存了未参与分配的客户记录。只要稍微改一下，完全可以满足楼主的要求的哦。
    至于每个员工的客户数是一次分配就予以填满，还是多次平均分配以达最佳效果，是不同的算法范畴，运行结果也稍有不同，在此不再赘叙。

lolo

附件：数值分配的问题2.xls.txt 是excel表格，改名成：数值分配的问题2.xls 就可以了。

dishuo

原帖由 simplemen 于 2008-9-19 00:06 发表
楼上可以告诉我，你用的什么编辑器么，一直想找个这种有语法高亮，最好是有关键字提示的编辑器，可是别的语言都有，唯独批处理没有，

我用的是 Notepad2 MOD v1.1.0.8简体中文版

alex_liuzhong

excel 的 规划求解 可以很简单的完成操作。

nopr

我觉得不一定要非得是35000万，，可以是3400-3600之间就行了。最后再把剩下的加给小于35000的就可以了吧。。
不过还真不好写，，