Bin Packing Problem Java

Assigning some items with known weights to bins with consistent capacities is necessary for the bin packing problem. The goal is to use the smallest possible boxes while ensuring everything is put away. It is an example of an NP-hard problem.

Example:

Arr[]={4,8,1,4,2,1}

Bin capacity=10

Output: 2

There are possibilities from the given weighted array. They are {4,4,2}, and the other possibility is {8,1,1}. Hence it is required a minimum of 2 bins is needed.

Lower Bound

There is always a minimum amount of bins that can be found. The lower bound is as follows:

A minimum number of bins >=  (Total Weight / Bin Capacity).

Applications

• Loading trucks or containers.
• Data storage over several discs.
• Job planning.
• Placing commercials during set radio/TV station breaks.
• Putting music library on cassettes, CDs, etc

Online Algorithms

These are the Algorithms for bin packing issues, where each item must be placed in a bin before moving on to the next when it arrives one at a time (in a pending order).

1. Next Fit

Before processing the following item, ensure it will fit in the same bin as the preceding one. If it doesn't, only use a fresh bin.

Filename: BinsRequired1.java

//Java Program for finding the number of bins required using the Next fit algorithm
class BinsRequired1 {
	// The algorithm displays the number of bins required
	static int nextFits(int weights[], int num, int count)
	{
		// the result and the count of bins are initialized
		int result = 0, bin_rems = count;
		//the values are placed one after the other
		for (int i = 0; i < num; i++) {
			// checking the limit of the bin
			if (weights[i] > bin_rems) {
				result++; // Use a new bin
				bin_rems = count - weights[i];
			}
			else
				bin_rems -= weights[i];
		}
		return result;
	}
	// Main section of the Program
	public static void main(String[] args)
	{
		int weights[] = { 5, 5, 3, 7, 1, 2, 5 };
		int count = 9;
		int num = weights.length;
		System.out.println("The Number of bins required using Next Fit: " + nextFits(weights, num, count));
	}
}

Output

The Number of bins required using Next Fit: 3

Time Complexity: O(N)

Space Complexity:O(1)

Explanation

It is the easiest approach. Twice the ideal number bounds the number of bins employed by this technique, or Next Fit is about 2 in number. Take any two nearby bins as an example. Because NextFit would have moved every item from the second bin into the first if the sum of the things in these two bins were c. For every other bin, the same applies. Accordingly, if M is ideal, Next Fit uses no more than 2M bins because the maximum amount of space is wasted.

2. First Fit

Place the object in the first bin that fits while processing the following item. This is done by scanning the preceding bins in succession. Only begin a new bin if no current bins will contain it.

Filename: BinsFirstFit.java

//Program for finding the number of bins required using the First Fit Algorithm
class BinsRequired2
{
// displays the number of bins required using the First Fit Algorithm
static int firstFits(int weights[], int num, int count)
{
	// the result and the count values are initialized
	int result = 0;
	// an array is created for storing the bin values
	int []bin_rems= new int[num];
	//the item are placed one by one
	for (int i = 0; i < num; i++)
	{
		// Initial bin is identified
		int j;
		for (j = 0; j < result; j++)
		{
			if (bin_rems[j] >= weights[i])
			{
				bin_rems[j] = bin_rems[j] - weights[i];
				break;
			}
		}
		// Condition if the bin can't fit
		if (j == result)
		{
			bin_rems[result] = count - weights[i];
			result++;
		}
	}
	return result;
}
// Main section of the Program
public static void main(String[] args)
{
	int weights[] = { 1, 5, 4, 4, 1, 5, 9 };
	int count = 11;
	int num = weights.length;
	System.out.print("The Number of bins required in First Fit: "+ firstFits(weights, num, count));
}
}

Output

The Number of bins required in First Fit: 3

Time Complexity: O(N*N)

3. Best Fit

The objective is to position the following item in the *tightest* space. In other words, please place it in the trash can with the least space remaining.

Filename: BinsRequired3.java

//Program for finding the number of bins required using the Best Fit Algorithm
class BinsRequired3
{
// displays the number of bins required using the best-fit algorithm
static int bestFits(int weights[], int num, int count)
{
	// the result value is initiated
	int result = 0;
	// create an array to hold the remaining space in bins; the maximum number of bins is num.
	int []bin_rems = new int[num];
	//the items are placed after the other
	for (int i = 0; i < num; i++)
	{
		// the bin which will satisfy the condition
		int j;
		// The minimum space for bins
		int minimum = count + 1, bin = 0;
		for (j = 0; j < result; j++)
		{
			if (bin_rems[j] >= weights[i] &&
				bin_rems[j] - weights[i] < minimum)
			{
				bin = j;
				minimum = bin_rems[j] - weights[i];
			}
		}
		//If the bin does not use the value, another bin is created
		if (minimum == count + 1)
		{
			bin_rems[result] = count-weights[i];
			result++;
		}
		else 
			bin_rems[bin] -= weights[i];
	}
	return result;
}
public static void main(String[] args)
{
	int []weights = { 3, 6, 4, 5, 7, 2, 9 };
	int count = 15;
	int num = weights.length;
	System.out.print("The Bins required in Best Fit: "+ bestFits(weights, num, count));
}
}

Output

The Bins required in Best Fit: 3

Time Complexity: O(N log N)

4. Worst Fit

To balance the bins, place the estimates of the long in the least crowded area. And put it in the trash can so that most of the space is left empty.

Filename: BinsRequired4.java

///Program for finding the number of bins required using the Worst Fit Algorithm
class BinsRequired4
{
// displays the bins required in Worst Fit Algorithm
static int worstFits(int weights[], int num, int count)
{
	// the result value is initialized
	int result = 0;
	// Create an array to hold the rest of the space in bins
	//the maximum number of bins is n.
	int bin_rems[]= new int[num];
	//the items are placed one after the other
	for (int i = 0; i < num; i++)
	{
		//The bin which will accommodate the required value is selected
		int j;
		// the maximum place variable is assigned to -1
		int max = -1, win = 0;
		for (j = 0; j < result; j++) {
			if (bin_rems[j] >= weights[i] && bin_rems[j] - weights[i] > max) {
				win = j;
				max = bin_rems[j] - weights[i];
			}
		}
		// if the condition fails new bin created
		if (max == -1) {
			bin_rems[result] = count - weights[i];
			result++;
		}
		else 
			bin_rems[win] -= weights[i];
	}
	return result;
}
public static void main(String[] args)
{
	int weights[] = { 1, 2, 7, 4, 1, 2, 9 };
	int count = 10;
	int num = weights.length;
	System.out.print("The Bins Required in Worst Fit are: " +worstFits(weights, num, count));
}
}

Output

The Bins Required in Worst Fit are: 3

Time Complexity: O(N Log N)

Offline Methods

We have every element up front in the offline versions. The offline version is NP-Complete, which is unfortunate, but we have a better approximation approach. First Fit Decreasing employs a maximum of (4M + 1)/3 bins if the optimal is M.

5. First Fit Decreasing

One issue with online techniques is that packing big items can be challenging, particularly if they come up late in the sequence. We can get around this by "sorting" the input sequence and placing the bulky items at the top. Sorting produces First Fit Decreasing and Best Fit Decreasing, the offline equivalents of online First Fit and Online Best Fit.

Filename: BinsFirstFitDecreasing.java

//Program for finding the number of bins required using First Fit Decreasing
import java.util.*;
class BinsFirstFitDecreasing
{
	static int firstFits(Integer weights[], int num, int count)
        {
	// the result and the count values are initialized
	int result = 0;
	// an array is created for storing the bin values
	int []bin_rems= new int[num];
	//the item are placed one by one
	for (int i = 0; i < num; i++)
	{
		// Initial bin is identified
		int j;
		for (j = 0; j < result; j++)
		{
			if (bin_rems[j] >= weights[i])
			{
				bin_rems[j] = bin_rems[j] - weights[i];
				break;
			}
		}
		// Condition if the bin can't fit
		if (j == result)
		{
			bin_rems[result] = count - weights[i];
			result++;
		}
	}
	return result;
         }
	static int firstFitDecs(Integer weights[], int num, int count)
	{
		// The weights are arranged in sorted order
		Arrays.sort(weights, Collections.reverseOrder());
		// Now call first fit for sorted items
		return firstFits(weights, num, count);
	}
	// Main section
	public static void main(String[] args)
	{
		Integer weights[] = { 1, 3, 4, 8, 7, 5, 4};
		int count = 9;
		int num = weights.length;
		System.out.print("The Bins used in First Fit " + "Decreasing : "+ firstFitDecs(weights, num, count));
	}
}

Output

The Bins used in First Fit Decreasing: 4

Time complexity: O(N Log N)