Click here to Skip to main content
Rate this: bad
good
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
Edited 8-Oct-11 22:39pm
Mehdi Gholam253.3K
v2
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

See the answers to the following question :
Best Fitting Strings into a Text Message[^]
  Permalink  
Comments
André Kraak at 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
good
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.
  Permalink  
Comments
Mehdi Gholam at 9-Oct-11 5:16am
   
nice, 5!
Rate this: bad
good
Please Sign up or sign in to vote.

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 
  Permalink  

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

  Print Answers RSS
0 OriginalGriff 245
1 Kamal Rocks 184
2 Sergey Alexandrovich Kryukov 175
3 BillWoodruff 173
4 PIEBALDconsult 160
0 OriginalGriff 5,695
1 DamithSL 4,506
2 Maciej Los 4,007
3 Kornfeld Eliyahu Peter 3,480
4 Sergey Alexandrovich Kryukov 3,180


Advertise | Privacy | Mobile
Web03 | 2.8.141216.1 | Last Updated 9 Oct 2011
Copyright © CodeProject, 1999-2014
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