See the answers to the following question :

Best Fitting Strings into a Text Message[^]

16,018,318 members

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

Permalink

Share this answer

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.

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.

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.

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

Share this answer

Comments

Mehdi Gholam
9-Oct-11 5:16am

nice, 5!

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

Share this answer

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

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900