Bin Packing Problem (How to minimize the number of used Bins)

You have been given an array. The values of the array represent the size of n different items. You have been also given some bins. You have to store the items in the bins such that there will be minimum number of used bins. Maximum capacity of a bin will be given. The size of an item will not exceed the capacity of a bin.

Input- [ 2, 3, 5, 8, 13, 10, 1, 4]   capacity of the bin= 15

Output- 4

Explanation

The packing of bins are as follows:

bin1: 13, 2

bin2:  10, 1, 4

bin3:  3, 5

bin4:  8

It is possible to arrange the items between these bins in different ways. But it is obvious that we need minimum 4 bins.

Algorithm

Step 1: Start

Step 2: The size of array is taken from the user

Step 3: Values of array is taken from the user

Step 4: We sort the array

Step 5: We check the items from maximum size element.

Step 6: In this way we traverse the array and find the total count of used bins.

Step 7: Stop.

Explanation of the Algorithm

This is a NP hard problem. We sort the array first and check from maximum element after that we check if next element can be packed in the same bin or not. If not then we have to allocate one more bin. In this way we calculate the number of bins.

Code

// C++ program to find minimum number of bins to pack items

Program in C++

#include <bits/stdc++.h>
using namespace std;
int firstFit(int weight[], int n, int c)
{
    int res = 0;
    int bin_rem[n];
    for (int i = 0; i < n; i++) {
        
        int j;
        for (j = 0; j < res; j++) {
            if (bin_rem[j] >= weight[i]) {
                bin_rem[j] = bin_rem[j] - weight[i];
               
                break;
            }
        }


        if (j == res) {
            bin_rem[res] = c - weight[i];
            res++;
        }
       
    }
    return res;
}
int firstFitDec(int weight[], int n, int c)
{
	sort(weight, weight + n, std::greater<int>());
	return firstFit(weight, n, c);
}
int main()
{
	int weight[] = { 2, 3, 5, 8, 13, 10, 1, 4};
	int c = 10;
	int n = sizeof(weight) / sizeof(weight[0]);
	cout << " Total numbers of required bin: -> " << firstFitDec(weight, n, c);
	return 0;
}

//Java program to find the minimum number of bins to pack items

Program in Java

import java.util.*;
class bn
{
	static int firstFit(int weight[], int n, int c)
{
    int res = 0;
    int []bin_rem = new int[n];
    for (int i = 0; i < n; i++)
    {
        int j;
        for (j = 0; j < res; j++)
        {
            if (bin_rem[j] >= weight[i])
            {
                bin_rem[j] = bin_rem[j] - weight[i];
                break;
            }
        }
 
        if (j == res)
        {
            bin_rem[res] = c - weight[i];
            res++;
        }
    }
    return res;
}
	static int firstFitDec(Integer weight[], int n, int c)
	{
		Arrays.sort(weight, Collections.reverseOrder());
		
		return firstFit(weight, n, c);
	}
	public static void main(String[] args)
	{
		Integer weight[] = { 2, 3, 5, 8, 13, 10, 1, 4};
		int c = 10;
		int n = weight.length;
		System.out.print("Total numbers of required bin: -> "
		+ firstFitDec(weight, n, c));
	}
}

# Python program to find minimum number of bins to pack items

Program in Python

def firstFit(weight, n, c):
	res = 0
	bin_rem = [0]*n
	
	for i in range(n):	
		j = 0
		while( j < res):
			if (bin_rem[j] >= weight[i]):
				bin_rem[j] = bin_rem[j] - weight[i]
				break
			j+=1			
		if (j == res):
			bin_rem[res] = c - weight[i]
			res= res+1
	return res	
def firstFitDec(weight, n, c):
	weight.sort(reverse = True)
	return firstFit(weight, n, c)
weight = [ 2, 3, 5, 8, 13, 10, 1, 4]
c = 10
n = len(weight)
print("Total numbers of required bin: -> ",str(firstFitDec(weight, n, c)))

// C# program to find minimum number of bins to pack items

Program in C#

using System;
public class bn
{
	static int firstFitDec(int []weight, int n, int c)
	{	
		Array.Sort(weight);
		Array.Reverse(weight);	
		return firstFit(weight, n, c);
	}
	static int firstFit(int []weight, int n, int c)
	{
		int res = 0;
		int []bin_rem = new int[n];
		for (int i = 0; i < n; i++)
		{
			int j;
			for (j = 0; j < res; j++)
			{
				if (bin_rem[j] >= weight[i])
				{
					bin_rem[j] = bin_rem[j] - weight[i];
					break;
				}
			}
			if (j == res)
			{
				bin_rem[res] = c - weight[i];
				res++;
			}
		}
		return res;
	}
	public static void Main(String[] args)
	{
		int []weight = { 2, 3, 5, 8, 13, 10, 1, 4};
		int c = 10;
		int n = weight.Length;
		Console.Write("Total numbers of required bin: -> "
		+ firstFitDec(weight, n, c));
	}
}

Output: 

Total numbers of required bin:  4