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

dishuo

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

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