Click here to Skip to main content
12,694,121 members (34,534 online)
Rate this:
Please Sign up or sign in to vote.
See more: C# ASP .NET
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 21:47pm
Updated 8-Oct-11 22:39pm
Rate this: bad
Please Sign up or sign in to vote.

Solution 1

See the answers to the following question :
Best Fitting Strings into a Text Message[^]
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.
Rate this: bad
Please Sign up or sign in to vote.

Solution 2

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.
Mehdi Gholam 9-Oct-11 5:16am
nice, 5!
Rate this: bad
Please Sign up or sign in to vote.

Solution 3

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

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

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

 if (@RunningTotal +@Salary > 5000)
		SET @GroupCount=@GroupCount+1
		SET @RunningTotal = @Salary
		SET @RunningTotal = @RunningTotal + @Salary
	update #temp
	set Grouped='Group ' + STR(@GroupCount)
	where ID=@ID
  FETCH NEXT FROM rt_cursor INTO @ID,@Salary

CLOSE rt_cursor
DEALLOCATE rt_cursor
select * from #temp 

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

  Print Answers RSS
Top Experts
Last 24hrsThis month

Advertise | Privacy | Mobile
Web02 | 2.8.170118.1 | Last Updated 9 Oct 2011
Copyright © CodeProject, 1999-2017
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100