Assignment on
Bin packing problem
Course Title: Design and Analysis of Algorithms
Course Code: CSE 3203
Md. Habibur Rahman
ID: 1505001
Introduction
The fundamental aim of bin packing is to pack a collection of objects into well defined regions
called bins, so that they do not overlap. Packing algorithms sound intimidating and for good
reason. In popular culture, we associate algorithms with complex, advanced technology. In
reality, an algorithm is just a means of solving problems really quickly. In the world of supply
chain management, packing algorithms help warehouse managers address what’s known as the
bin packing problem— the issue of packing multiple items of various sizes into a finite number
of bins (in this case, shipping boxes).
What is bin packing problem?
Bin packing problem consider sets of objects and containers called bin and the aim is to group
objects in such a way that they all fit into the minimum number of bins. Usually, the critical aim
is to make efficient use of space or time. A bin can not only be a container, but could represent a
space in time or a surface area. So in the real world the packing must be without overlaps
between goods and other goods or the container walls.
Given n items with sizes S1,S2,…..Sn such that 0 ≤ Si ≤ 1 for 1 ≤ i ≤ n, pack them into the
fewest number of unit capacity bins.
The bin packing problem consists of packing items of varying sizes into a finite number of bins
of fixed capacity. The objective is to minimize the number of bins used to pack all the items.
Approximation algorithms allow for getting a solution close to the optimal solution of an
optimization problem in polynomial time. For given problem instance I, Approximation Ratio is
the ratio of algo(I) and opt(I).
Approximation ratio = algo(I) / opt(I)
These problems are optimization problems with many practical applications related to real life as
stock cutting, scheduling tasks, layouts on computer chips, packing goods into crates, assigning
commercials to station breaks on television, loading trucks with a given size or weight limit and
storage problems. The list is endless and extremely diverse.
There are many variations of the problem. Items may be packed by weight or price. Items may
be fragmented and packed separately for a certain cost. When packed together, items may
occupy less space such as the case in VM (virtual machine) packing. The most common
variations of the bin packing problem are:
Knapsack
1-Dimensional Bin Packing
Cutting Stock Problem
Variable Size Bin Packing Problem (VSBPP)
2-Dimensional Bin Packing Problem
Overview of Standard Bin Packing Algorithms
Bin packing algorithm are categorized by the specific bin packing strategy they facilities.
First Fit Bin Packing Algorithm
When processing the next element, examine or scan the previous bins in order and place the
element in the first bin that fits. If element does not fit in any of the existing bins at that time we
start a new bin only or otherwise When packing an item, start with the earliest bin. For instance,
if you have a row of boxes partially filled with various items, check to see if it fits in the very
first box you packed (Bin 1). If it doesn’t move on to Bin 2, and down the row until you find one
that works.
Example: Items - 0.5, 0.3, 0.4, 0.8, 0.2, 0.2, 0.2 and bin capacity 1
0.2
0.3 0.2
0.2
0.5
0.4 0.8
Bin 1 Bin 2 Bin 3
Next Fit Bin Packing Algorithm
The idea behind this algorithm is place the items into it in the order they appear in the list. The
worker checks if an item fits in the bin they’re currently filling. If it does fit, they place it in. If it
doesn’t, they close that box and use the next one. With this strategy, a worker never returns to a
previous bin. For instance, if they can’t fit an item in Bin 4, they don’t return to Bin 3. They
simply grab a new one.
The benefit of this method is that you don’t need a lot of dedicated warehouse space. The minute
additional items cannot fit into the bin, it’s shipped off to the end customer.
Example: Items – 0.4, 0.7, 0.1, 0.3, 0.8, 0.2, 0.5 and bin capacity 1
0.3
0.2
0.1 0.5
0.7
0.4
Bin1 Bin 2 Bin 3
Worst Fit Bin Packing Algorithm
Worst Fit packs the input item according to the following rule: while trying to pack item ai, the
worst fit algorithm assigns the item to the bin whose empty space is maximum. If the item ai is
unable to fit in any of the opened bins, then a new bin is opened to pack that item ai.
Example: Items – 0.4, 0.7, 0.1, 0.3, 0.8, 0.2, 0.5 and bin capacity 1
0.3
0.2
0.8 0.5
0.1
0.7
0.4
Bin 1 Bin 2 Bin 3 Bin 4
Best Fit Bin Packing Algorithm
Best Fit packs the input item according to the following rule: while trying to pack item a i, the
best fit algorithm assigns the item to the bin whose empty space is minimum. If the item a i is
unable to fit in any of the opened bins, then a new bin is opened to pack that item ai.
Example: Items – 0.2, 0.5, 0.4, 0.1, 0.3, 0.8 and bin capacity 1
0.3
0.1 0.8
0.5 0.4 0.7
0.2
Bin 1 Bin 2 Bin 3 Bin 4
Problem about Bin Packing
https://onlinejudge.org/external/11/1149.pdf
This is the problem link of uva bin packing problem. In this problem there are several items with
different weight is given. We need to find out the minimum number of bin are require to pack
them in it. So the solution is given below.
Problem Solution
#include<bits/stdc++.h>
using namespace std;
int main()
int t;
cin>>t;
while(t--)
int n;
cin>>n;
int x;
cin>>x;
int arr[100000+5];
for(int i=0;i<n;i++)
cin>>arr[i];
sort(arr,arr+n);
int l=0,r=n-1;
int ans=0;
while(l<=r)
if(arr[l]+arr[r]<=x)
l++;
r--;
else r--;
ans++;
cout<<ans<<endl;
if(t)cout<<endl;
return 0;
Sample Output:
