如何形成不超过最大值的最小组 [英] How to Form Minimum Groups which should not exceed a max value

问题描述

我有一个如下数据表

I have a datatable like below

Employee           Salary
--------------------------
Emp A              1000
Emp B              500
Emp C              3000
Emp D              3000
Emp E              200
Emp F              100
Emp G              200
Emp H              500
Emp I              1450

我想要最少的组数，一组的薪金总和不应该超过5000.所以我的最终输出应该是这样的

I want minimum number of groups, Sum of Salary in one group should not exceed 5000. So my final output should be like this

Employee           Salary       Group
-------------------------------------
Emp A              1000	        Group 1
Emp B	           500	        Group 1
Emp C	           3000	        Group 1
Emp E	           200	        Group 1
Emp F	           100	        Group 1
Emp G	           200	        Group 1
		
Emp D	           3000	        Group 2
Emp H	           500	        Group 2
Emp I	           1450	        Group 2

我怎样才能做到这一点?请引导我

How can I achieve this? Please guide me

推荐答案

查看以下问题的答案:
最佳将字符串匹配到文本消息中 [ ^ ]

See the answers to the following question :
Best Fitting Strings into a Text Message[^]

Mehdi答案和最佳拟合算法 [ ^ ]是一个很好的起点.

但是，从所使用的示例中可以看出，该算法并不总是能够给出最佳答案.
因此，在运行算法之后，再次遍历这些垃圾箱，看看是否可以将它们清空到其他垃圾箱中.使用相同的原理将值放置在最满的容器中.

在算法示例的情况下，您可以清空第3组，而只剩下一个箱即可使用.

Mehdi answer and the Best Fit Algorithm[^] is an excellent starting point.

But the algorithm will not always give the optimal answer as you can see from the example used.
So after having run the algorithm iterate through the bins once more and see if you can empty them into the other bins. Used the same principle of placing the value in the most filled bin.

In case of the algorithm example you can empty group 3, leaving you with one less bin to use.

这行得通，但是不确定性能?...

This works but not sure about the performance ?...

Create procedure Test as
DECLARE @ID int,
        @Salary money,
        @RunningTotal money,
		@GroupCount int
		
SET @RunningTotal = 0
SET @GroupCount=1

DECLARE rt_cursor CURSOR
FOR SELECT ID, Salary FROM employee
order by ID

select ID, SPACE(50) Grouped into #temp from employee
OPEN rt_cursor

FETCH NEXT FROM rt_cursor INTO @ID,@Salary

WHILE @@FETCH_STATUS = 0
 BEGIN
 if (@RunningTotal +@Salary > 5000)
	Begin
		SET @GroupCount=@GroupCount+1
		SET @RunningTotal = @Salary
	End
 else
	Begin
		SET @RunningTotal = @RunningTotal + @Salary
	End
	update #temp
	set Grouped=''Group '' + STR(@GroupCount)
	where ID=@ID
	
	
	
  FETCH NEXT FROM rt_cursor INTO @ID,@Salary
 END

CLOSE rt_cursor
DEALLOCATE rt_cursor
select * from #temp 

这篇关于如何形成不超过最大值的最小组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！