Board logo

标题: 批处理如何平均分配不同数值 [打印本页]
作者: myweb9169    时间: 2007-12-30 22:37     标题: 批处理如何平均分配不同数值

俺公司老总让我给甲公司编一个程序，情况是：甲公司有20个员工，一万个客户，每个客户购买量不等，有的2个亿，有的几千万，有的几万，共计70亿，现在要求把这些客户分给每一个员工，分完后每个员工的客户购买量必须是金额相等的，但客户数量不要求相等，求助各位老大，批处理能做到吗，如果能给俺批一下吧，如果不行，能不能，告诉俺，什么语言能做到，关系重大啊，先谢谢各位老大了
作者: youxi01    时间: 2007-12-30 23:07

起码来说，要把各位客户购买量的具体数字　发出来
作者: myweb9169    时间: 2007-12-30 23:18

太多了，老大，保存在公司电脑里
作者: youxi01    时间: 2007-12-30 23:55

那怎么算？连具体的数据都没有！
作者: 随风    时间: 2007-12-31 00:38

首先,这些购买量是否都是整数?
最起码要给出一部分购买量的样本.比如是什么格式.
但必须是能用记事本打开的.
另:70亿,好像已经是个超大数了吧.
作者: myweb9169    时间: 2007-12-31 00:49

原帖由 随风 于 2007-12-31 00:38 发表
首先,这些购买量是否都是整数?
最起码要给出一部分购买量的样本.比如是什么格式.
但必须是能用记事本打开的.
另:70亿,好像已经是个超大数了吧.

太多了，在公司的办公电脑里，能不能假设他就在a.txt里，格式为，一号客户   xxx万 二号客户  xxxx万
一直到一万号  xxxx万，行吗？
可以精确到万位
作者: youxi01    时间: 2007-12-31 00:50

你只要了解算法就行了嘛
你没必要将数据全部发出来，只要发部分就行了...
作者: 随风    时间: 2007-12-31 00:56

格式要清楚,比如是如何分行的?
如
一号客户   xxx万
二号客户  xxxx万
一直到一万号  xxxx万
和
一号客户   xxx万 二号客户  xxxx万  一直到一万号  xxxx万
是不一样的.
另外,数字是1万还是10000  ???
作者: myweb9169    时间: 2007-12-31 00:58

原帖由 youxi01 于 2007-12-31 00:50 发表
你只要了解算法就行了嘛
你没必要将数据全部发出来，只要发部分就行了...

原表格很复杂，至少有10几项，不过我能把它精简到这样a.txt
一号客户：xxxx万
二号客户：xxxx万
.........................
10000号：xxxx万
合计：10000户  70亿
作者: myweb9169    时间: 2007-12-31 01:04

原帖由 随风 于 2007-12-31 00:56 发表
格式要清楚,比如是如何分行的?
如
一号客户   xxx万
二号客户  xxxx万
一直到一万号  xxxx万
和
一号客户   xxx万 二号客户  xxxx万  一直到一万号  xxxx万
是不一样的.
另外,数字是1万还是10000  ???

是9楼那样的格式，纯数字的比如：16987万元，万元两个字我可以把它替换为空
几位老大真是费心，谢谢
作者: 随风    时间: 2007-12-31 01:29

仔细想了想,发现好像很难实现,
70亿除以20等于350000000
即要求每位员工要分配350000000金额.
但如果没有金额加起来正好等于350000000的,怎么办?
作者: youxi01    时间: 2007-12-31 01:38

大致相等就行了
作者: myweb9169    时间: 2007-12-31 01:49

大致相等就行了，可以去掉4个0，比如35000000，写成35000，完后我自己再给加上万元字样，我觉得主要是不是客户太多了
作者: myweb9169    时间: 2007-12-31 02:08

也问过别人怎么算，给了个算法，先把客户这样分
客户1      22000万   购买量第一大的
客户2      19000万    购买量第二大的
.................................................................
客户10000  23万    最小购买量
然后  把客户1的购买量和客户10000的购买量相加，把客户2和客户9999号相加，以此类推，一直加到3500万，然后把这些客户去掉，在这样相加，加到3500，再去，在加，说这样能给分出来，我也没正懂对不对，希望能有点参考作用，
作者: youxi01    时间: 2007-12-31 09:33

当然,楼上的方法是个好方法,但难度照样太大
其实,这个题目,很早就有人提过(CCWAN在联盟里),但是因为难度问题,没人敢回答...
作者: 小竹    时间: 2007-12-31 11:12

现将一万个客户由大到小排序，设为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    时间: 2007-12-31 11:19

楼上的方式还是不太合理
原来有人提出思路:先排序,然后加一个最大的，再加个最小的，这种方式比较合理,更容易求出近似解...
作者: 小竹    时间: 2007-12-31 11:36     标题: 回复 17# 的帖子

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

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

本来的思路就是这样的...
作者: dishuo    时间: 2008-8-20 21:32

思路：读取数据，排序，由大到小开始分配给员工，员工的查找顺序为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    时间: 2008-9-19 00:06

楼上可以告诉我，你用的什么编辑器么，一直想找个这种有语法高亮，最好是有关键字提示的编辑器，可是别的语言都有，唯独批处理没有，
作者: lolo    时间: 2008-9-26 10:32

都用上Excel了，为什么不用VBA呢？
  1. Sub allocate2() '假设数据区域从大到小排序

  2. Dim employee(19), m(19)

  3. For i = 0 To 19

  4. Set employee(i) = CreateObject("Scripting.Dictionary")

  5. Next i

  6. Set lost = CreateObject("Scripting.Dictionary")

  7. NUM = Application.InputBox("请输入客户数：", "选择运算范围", 580, , , , , 9)

  8. If NUM < 20 Then MsgBox "请重新选择", , "选择有误!"

  9. avg = Application.WorksheetFunction.Sum(Range("b1:b" & NUM)) / 20

  10. guest = Range("a1:b" & NUM)

  11. i = -1

  12. For n = 1 To NUM

  13. flag = False

  14. t = 1

  15. Do While t <= 20

  16. i = (i + 1) Mod 20

  17. If m(i) + guest(n, 2) <= avg Then

  18. m(i) = m(i) + guest(n, 2)

  19. employee(i).Add guest(n, 1), guest(n, 2)

  20. flag = True

  21. Exit Do

  22. End If

  23. t = t + 1

  24. Loop

  25. If flag = False Then

  26. lost.Add guest(n, 1), guest(n, 2)

  27. End If

  28. Next n

  29. End Sub
复制代码
作者: lolo    时间: 2008-9-26 10:45     标题: 回复 23楼 的帖子

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

附件：数值分配的问题2.xls.txt 是excel表格，改名成：数值分配的问题2.xls 就可以了。
作者: dishuo    时间: 2008-11-28 21:33

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

我用的是 Notepad2 MOD v1.1.0.8简体中文版
作者: alex_liuzhong    时间: 2009-4-13 17:10

excel 的 规划求解 可以很简单的完成操作。
作者: nopr    时间: 2009-8-7 13:44

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



欢迎光临 批处理之家 (http://bathome.net./) Powered by Discuz! 7.2