这个任务实际上是科学的（包装问题，或一种），可能更适合 math.stackexchange :)
我的解决方案分为两个步骤（与许多优化问题一样） - 找到一些初始解决方案并尝试对其进行改进。
初步解决方案：
ServerName GroupNo TotalSizeGB
---------- ----------- -----------
Server1 3 123.45
Server2 3 234.56
Server3 2 345.67
Server4 1 456.78
Server5 2 567.89
Server6 1 678.90
Server7 3 789.01
Server8 3 890.12
Server9 1 901.23
Server10 2 1023.35
GroupNo GroupSizeGb
----------- -----------
1 2036.91
2 1936.91
3 2037.14
优化：
ServerName GroupNo TotalSizeGB
---------- ----------- -----------
Server1 3 123.45
Server2 3 234.56
Server3 2 345.67
Server4 1 456.78
Server5 3 567.89
Server6 1 678.90
Server7 2 789.01
Server8 2 890.12
Server9 1 901.23
Server10 3 1023.35
GroupNo GroupSizeGb
----------- -----------
1 2036.91
2 2024.80
3 1949.25
不幸的是，我无法在 SQLFiddle 上设置它，因为使用了显式事务。
set nocount on
-- Parameters
declare
@nGroups int, -- Number of groups to split servers to
@tolerance float, -- let say 0.0 ... 0.1 (0.1 mean that (+/-)10% deviation allowed from target group size)
@nTries int, -- refinement tries 100, 1000, 10000 or as much as you can wait if you are not satisfied with initial solution
@mFactor float, -- refinement param 0.0 ... 1.0
@tolerance2 float -- let say 0.1 ... 0.3
set @nGroups = 3
set @tolerance = 0
set @nTries = 1000
set @mFactor = 0.3
set @tolerance2 = 0.3
-- Initial Data
create table #Servers (ID int identity, ServerName sysname, TotalSizeGB decimal (12,2), primary key clustered(ID))
insert into #Servers (ServerName, TotalSizeGB) values
('Server1',123.45),
('Server2',234.56),
('Server3',345.67),
('Server4',456.78),
('Server5',567.89),
('Server6',678.90),
('Server7',789.01),
('Server8',890.12),
('Server9',901.23),
('Server10',1023.35)
create table #Groups (GroupNo int not NULL, primary key clustered (GroupNo))
insert into #Groups (GroupNo)
select N from (select row_number() over (order by @@spid) from sys.all_columns) S(N) where N <= @nGroups
create table #ServerGroups (ServerID int not NULL, GroupNo int not NULL, primary key clustered(ServerID))
create index #IX_GroupServers_GroupNo on #ServerGroups (GroupNo)
declare
@srvCnt int,
@grSize decimal (12,2),
@grNo int,
@grSz decimal (12,2),
@srvID int
select @srvCnt = count(1), @grSize = sum(TotalSizeGB) / @nGroups from #Servers
select @grSize as [Target approx. group size]
-- Find initial solution
while (select count(1) from #ServerGroups) < @srvCnt
begin
select top 1 @grNo = g.GroupNo
from #Groups g
left join #ServerGroups sg on sg.GroupNo = g.GroupNo
left join #Servers s on s.ID = sg.ServerID
group by g.GroupNo
order by sum(s.TotalSizeGB)
select @grSz = IsNull(sum(s.TotalSizeGB), 0)
from #Groups g
left join #ServerGroups sg on sg.GroupNo = g.GroupNo
left join #Servers s on s.ID = sg.ServerID
where g.GroupNo = @grNo
select top 1 @srvID = ID
from #Servers s
where not exists (select 1 from #ServerGroups where ServerID = s.ID)
order by abs(@grSize - @grSz - s.TotalSizeGB)
insert into #ServerGroups (ServerID, GroupNo) values (@srvID, @grNo)
end
select g.GroupNo, SUM(s.TotalSizeGB) GroupSizeGb
from #Groups g
join #ServerGroups sg on sg.GroupNo = g.GroupNo
join #Servers s on s.ID = sg.ServerID
group by g.GroupNo
-- Refinement
declare @fTarg float
select @fTarg = sum(abs(case when abs(re) > @tolerance then re else 0 end))
from (
select g.GroupNo, SUM(s.TotalSizeGB) GroupSizeGb
from #Groups g
join #ServerGroups sg on sg.GroupNo = g.GroupNo
join #Servers s on s.ID = sg.ServerID
group by g.GroupNo
) t
cross apply (select (GroupSizeGb - @grSize)/@grSize re) p
print @fTarg
if @fTarg > 0
begin
create table #MServerGroups (ServerID int not NULL, GroupNo int not NULL, primary key clustered (ServerID))
insert into #MServerGroups
select ServerID, GroupNo from #ServerGroups
while @nTries > 0
begin
set @nTries = @nTries - 1
begin transaction
;with MS as (
select top (100*@mFactor) percent ServerID, GroupNo
from #MServerGroups
order by checksum(newid())
)
update msg
set
msg.GroupNo = case when msg.ServerID = tt.ServerID1 then tt.NewNo1 else tt.NewNo2 end
from
#MServerGroups msg
join (
select ServerID1, NewNo1, ServerID2, NewNo2
from (
select MS.ServerID as ServerID1, SS.GroupNo as NewNo1, SS.ServerID as ServerID2, MS.GroupNo as NewNo2, row_number() over (partition by SS.ServerID order by @@spid) as rn
from MS
join #Servers s on s.ID = MS.ServerID
cross apply (
select top 1 *
from
#Servers s2
join #MServerGroups ms2 on ms2.ServerID = s2.ID
where
s2.ID != MS.ServerID and ms2.GroupNo != MS.GroupNo and abs(s2.TotalSizeGB - s.TotalSizeGB)/s.TotalSizeGB < @tolerance2
order by checksum(newid())
) SS
) t
where rn = 1
)tt on msg.ServerID in (tt.ServerID1, tt.ServerID2)
if @@rowcount = 0
begin
rollback transaction
continue;
end
declare @fT float
select @fT = sum(abs(case when abs(re) > @tolerance then re else 0 end))
from (
select g.GroupNo, SUM(s.TotalSizeGB) GroupSizeGb
from #Groups g
join #MServerGroups sg on sg.GroupNo = g.GroupNo
join #Servers s on s.ID = sg.ServerID
group by g.GroupNo
) t
cross apply (select (GroupSizeGb - @grSize)/@grSize re) p
if @fT < @fTarg
begin
set @fTarg = @ft
print @fTarg -- the less this number, the better solution is
commit transaction
end
else
rollback transaction
end
update s
set s.GroupNo = m.GroupNo
from #MServerGroups m
join #ServerGroups s on s.ServerID = m.ServerID
select g.GroupNo, SUM(s.TotalSizeGB) GroupSizeGb
from #Groups g
join #ServerGroups sg on sg.GroupNo = g.GroupNo
join #Servers s on s.ID = sg.ServerID
group by g.GroupNo
drop table #MServerGroups
end
else
print 'No refinement needed'
drop table #Groups
drop table #ServerGroups
drop table #Servers
我建议从@nTries = 0合理的开始@tolerance（例如0.1、0.05）。