The bin packing problem asks for the minimum number k of identical bins of capacity C needed to store a finite collection of weights w_{1}, w_{2}, w_{3}, … , w_{n} so that no bin has weights stored in it whose sum exceeds the bin’s capacity. – Bin Packing (AMS).

for bins of size 10. No of bins required to store weights of size 3, 6, 2, 1, 5, 7, 2, 4, 1, 9?

When the number of bins is restricted to 1 and each item is characterized by both a volume and a value, the problem of maximizing the value of items that can fit in the bin is known as the knapsack problem

**Next-Fit Algorithm**:

Open a bin and place the items as they appear in the List. If an item on the list will not fit into the open bin, we close this bin permanently and open a new one and continue packing the remaining items in the list.

I have taken the images from the American Mathematical Society Article:

**First-Fit Algorithm**:

For First Fit the next item in the list into the first bin which has not been completely filled (thought of as numbered from left to right) into which it will fit. When bins are filled completely they are closed and if an item will not fit into any currently open bin, a new bin is opened

Implementation:

import java.util.*;
public class BinPacking
{
public static void main(String[] args)
{
System.out.println("Enter the number of items");
Scanner input = new Scanner(System.in);
int items=input.nextInt();
System.out.println("Enter the Size of the bin. All bins are of same size");
int size = input.nextInt();
System.out.println("Enter the items");
ArrayList< Integer> bin = new ArrayList< Integer>();
for(int member = 0; member < items ; member++)
{
bin.add(input.nextInt());
}
Collections.sort(bin);
int count = 0;
int binsize = items-1;
int i = 0;
while(i <= binsize)
{
int tmpsize = size;
tmpsize = tmpsize - bin.get(binsize--);
if(tmpsize >= bin.get(i))
{
i++;
}
count++;
}
System.out.println("The Minimum number of bins required is " +count);
}
}

> java BinPacking

Enter the number of items

10

Enter the Size of the bin. All bins are of same size

10

Enter the items

6

3

5

1

2

2

7

1

4

9

The Minimum number of bins required is 5

In MathWorld they indicate In 1973, J. Ullman proved that this algorithm can differ from an optimal packing by as much at 70% . An alternative strategy first orders the items from largest to smallest, then places them sequentially in the first bin in which they fit. In 1973, D. Johnson showed that this strategy is never suboptimal by more than 22%, and furthermore that no efficient bin-packing algorithm can be guaranteed to do better than 22%. – MathWorld

Below Solution shows the most optimal solution: 4 bins are actually needed !

References

1 . American Mathematical Society

2 . Wolfram MathWorld

### Like this:

Like Loading...

*Related*

Hi, I’m working on research about open source algorithms for packing problems pls I need to know about the license of your code for include in references

Thanks in advance for you response and time

You have those reversed – please revisit wiki as well as other documentation.