[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
12
返回列表 发帖
小竹

Rank: 3Rank: 3

帖子
42 
积分
296 
技术
1  
捐助
0  
注册时间
2007-12-30 
16楼 跳转到 »
发表于 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个员工分配完后，会剩下一些客户（不过这些客户的量都较小，量大已经被选走），那就按“最小加最大”的原则再分配。如此就可以得到近似解。

TOP

youxi01

Rank: 8Rank: 8

帖子
962 
积分
2449 
技术
40  
捐助
0  
注册时间
2007-10-25 
17楼
发表于 2007-12-31 11:19 | 只看该作者
楼上的方式还是不太合理
原来有人提出思路:先排序,然后加一个最大的，再加个最小的，这种方式比较合理,更容易求出近似解...

TOP

小竹

Rank: 3Rank: 3

帖子
42 
积分
296 
技术
1  
捐助
0  
注册时间
2007-12-30 
18楼
发表于 2007-12-31 11:36 | 只看该作者

回复 17# 的帖子

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

TOP

随风

Rank: 8Rank: 8

帖子
1759 
积分
5387 
技术
51  
捐助
210  
注册时间
2007-10-26 
19楼
发表于 2008-1-1 22:09 | 只看该作者
先说个思路看行不行
首先把这一万个客户倒排序,把7000个大的写入a.txt  把3000个小的写入b.txt
再把a.txt的第一个和最后一个相加,如果小于35000万,就再加第二个和倒数第二个,如果大于3500万,
就加b.txt的倒数第一个,依此类推....
技术问题请到论坛发帖求助！

TOP

youxi01

Rank: 8Rank: 8

帖子
962 
积分
2449 
技术
40  
捐助
0  
注册时间
2007-10-25 
20楼
发表于 2008-1-1 23:16 | 只看该作者
本来的思路就是这样的...

TOP

dishuo

Rank: 3Rank: 3

帖子
22 
积分
284 
技术
0  
捐助
0  
注册时间
2008-8-18 
21楼
发表于 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
高手=发现问题^分析问题^解决问题

TOP

simplemen

Rank: 2

帖子
5 
积分
177 
技术
0  
捐助
0  
注册时间
2008-9-7 
22楼
发表于 2008-9-19 00:06 | 只看该作者
楼上可以告诉我，你用的什么编辑器么，一直想找个这种有语法高亮，最好是有关键字提示的编辑器，可是别的语言都有，唯独批处理没有，

TOP

lolo

Rank: 2

帖子
4 
积分
185 
技术
0  
捐助
0  
注册时间
2008-9-8 
23楼
发表于 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
复制代码

TOP

lolo

Rank: 2

帖子
4 
积分
185 
技术
0  
捐助
0  
注册时间
2008-9-8 
24楼
发表于 2008-9-26 10:45 | 只看该作者

回复 23楼 的帖子

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

TOP

lolo

Rank: 2

帖子
4 
积分
185 
技术
0  
捐助
0  
注册时间
2008-9-8 
25楼
发表于 2008-9-26 10:57 | 只看该作者
附件：数值分配的问题2.xls.txt 是excel表格，改名成：数值分配的问题2.xls 就可以了。

TOP

dishuo

Rank: 3Rank: 3

帖子
22 
积分
284 
技术
0  
捐助
0  
注册时间
2008-8-18 
26楼
发表于 2008-11-28 21:33 | 只看该作者
原帖由 simplemen 于 2008-9-19 00:06 发表
楼上可以告诉我，你用的什么编辑器么，一直想找个这种有语法高亮，最好是有关键字提示的编辑器，可是别的语言都有，唯独批处理没有，

我用的是 Notepad2 MOD v1.1.0.8简体中文版
高手=发现问题^分析问题^解决问题

TOP

alex_liuzhong

Rank: 2

帖子
1 
积分
102 
技术
0  
捐助
0  
注册时间
2009-4-13 
27楼
发表于 2009-4-13 17:10 | 只看该作者
excel 的 规划求解 可以很简单的完成操作。

TOP

nopr

Rank: 2

帖子
33 
积分
184 
技术
0  
捐助
0  
注册时间
2009-8-1 
28楼
发表于 2009-8-7 13:44 | 只看该作者
我觉得不一定要非得是35000万，，可以是3400-3600之间就行了。最后再把剩下的加给小于35000的就可以了吧。。
不过还真不好写，，

TOP

12
返回列表