How to Form Minimum Groups which should not exceed a max value

Question

5.00/5 (2 votes)

See more:

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

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

Posted 8-Oct-11 20:47pm

Roshan P Mohammed

Updated 8-Oct-11 21:39pm

Mehdi Gholam

v2

Add a Solution

3 solutions

Solution 3

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

Posted 8-Oct-11 22:48pm

Bala Selvanayagam

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Mehdi Gholam · Accepted Answer · 2011-10-08T22:15:00

Solution 1

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

Posted 8-Oct-11 22:15pm

Mehdi Gholam

Comments

André Kraak 9-Oct-11 4:43am

my 5, excellent find.

Looking at the algorithm and the example used I suggest an optimization to the algorithm to meet the requirements of the OP, please see my solution.

André Kraak · Accepted Answer · 2011-10-08T22:40:00

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.