variation of bin packing problem
1 Answer
variation of bin packing problem
| Flag | PURGE
We have “k” bins and “n” objects where each bin has same capacity and capacity is equal to sum of weights of all “n” objects divided by k.
We need to pack these all “n” items in “k” bins such a way that all bins are equally heavy.
some test cases –
input –
5 items { 2,3,4,5,7 }
and 3 bins
output –
{ {7},{5,2},{3,4} }
input –
6 items { 4,4,4,4,4,5 }
and 5 bins
output –
NOT POSSIBLE
Email me when people comment.
Email me when people comment.
Loading...
An error occurred in subscribing you.
Email me when people comment.
Email me when people comment.
Loading...
An error occurred in subscribing you.
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
You can get all possible subsets of the input set.
The sum each value in each subset.
Add the subset to a Map<Integer,List<Set>>, where the key is the sum and the List contains the subset.
You can then iterate through the Map's values which is a List of Sets.
If the List of Sets size (e.g. List<Set>.size()) if equal to the 'bin' size and the List contains each element of the original Set then you have an answer.
- phishman3579 February 15, 2015