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)