Bin Packing Problem (Minimize number of used

Bins)
Last Updated : 02 Dec, 2024





Given n items of different weights and bins each of capacity c, assign

each item to a bin such that number of total used bins is minimized. It
may be assumed that all items have weights smaller than bin capacity.
Examples:
Input: weight[] = [4, 8, 1, 4, 2, 1], c = 10
Output: 2
Explanation: We need minimum 2 bins to accommodate all items. First
bin contains [4, 4, 2] and second bin [8, 1, 1].

Input: weight[] = [9, 8, 2, 2, 5, 4], c = 10

Output: 4
Explanation: We need minimum 4 bins to accommodate all items.

Input: weight[] = [2, 5, 4, 7, 1, 3, 8], c = 10

Output: 3
This problem is a NP-Hard problem and finding an exact minimum
number of bins takes exponential time. Following are
approximate algorithms for this problem.
Lower Bound
We can always find a lower bound on minimum number of bins required
as:
Min no. of bins >= Ceil ((Total Weight) / (Bin Capacity))
In the above examples, lower bound for first example is “ceil(4 + 8 + 1 +
4 + 2 + 1)/10” = 2 and lower bound in second example is “ceil(9 + 8 + 2
+ 2 + 5 + 4)/10” = 3.
Online Algorithms
These algorithms are for Bin Packing problems where items arrive one at
a time (in unknown order), each must be put in a bin, before considering
the next item.
1. Next Fit: When processing next item, check if it fits in the same bin as
the last item. Use a new bin only if it does not
Next Fit is a simple algorithm. It requires only O(n) time and O(1) extra space to
process n items.
Next Fit is 2 approximate, i.e., the number of bins used by this algorithm is
bounded by twice of optimal. Consider any two adjacent bins. The sum of items in
these two bins must be > c; otherwise, NextFit would have put all the items of
second bin into the first. The same holds for all other bins. Thus, at most half the
space is wasted, and so Next Fit uses at most 2M bins if M is optimal.
2. First Fit: When processing the next item, scan the previous bins in order and
place the item in the first bin that fits. Start a new bin only if it does not fit in any of
the existing bins.
The above implementation of First Fit requires O(n 2) time, but First Fit can be
implemented in O(n Log n) time using Self-Balancing Binary Search Trees.
If M is the optimal number of bins, then First Fit never uses more than 1.7M bins.
So First-Fit is better than Next Fit in terms of upper bound on number of bins.
Auxiliary Space: O(n)
3. Best Fit: The idea is to places the next item in the *tightest* spot. That is, put it
in the bin so that the smallest empty space is left.
Best Fit can also be implemented in O(n Log n) time using Self-Balancing Binary
Search Trees.
If M is the optimal number of bins, then Best Fit never uses more than 1.7M bins.
So Best Fit is same as First Fit and better than Next Fit in terms of upper bound on
number of bins.
Auxiliary Space: O(n)
4. Worst Fit: The idea is to places the next item in the least tight spot to even out
the bins. That is, put it in the bin so that most empty space is left.
Worst Fit can also be implemented in O(n Log n) time using Self-Balancing Binary
Search Trees.
If M is the optimal number of bins, then Best Fit never uses more than 2M-2 bins.
So Worst Fit is same as Next Fit in terms of upper bound on number of bins.
Auxiliary Space: O(n)
Offline Algorithms
In the offline version, we have all items upfront. Unfortunately offline version is also
NP Complete, but we have a better approximate algorithm for it. First Fit
Decreasing uses at most (4M + 1)/3 bins if the optimal is M.
1. First Fit Decreasing:
A trouble with online algorithms is that packing large items is difficult, especially if
they occur late in the sequence. We can circumvent this by *sorting* the input
sequence, and placing the large items first. With sorting, we get First Fit
Decreasing and Best Fit Decreasing, as offline analogues of online First Fit and
Best Fit.
First Fit decreasing produces the best result for the sample input because items
are sorted first.
First Fit Decreasing can also be implemented in O(n Log n) time using Self-
Balancing Binary Search Trees.
Auxiliary Space: O(1)
 Travelling Salesman Problem | Greedy Approach
he travelling salesman problem is a graph computational problem where the salesman
needs to visit all cities (represented using nodes in a graph) in a list just once and the
distances (represented using edges in the graph) between all these cities are known.
The solution that is needed to be found for this problem is the shortest possible route in
which the salesman visits all the cities and returns to the origin city.

If you look at the graph below, considering that the salesman starts from the vertex ‘a’,
they need to travel through all the remaining vertices b, c, d, e, f and get back to ‘a’
while making sure that the cost taken is minimum.

There are various approaches to find the solution to the travelling salesman problem:
naive approach, greedy approach, dynamic programming approach, etc. In this tutorial
we will be learning about solving travelling salesman problem using greedy approach.

Travelling Salesperson Algorithm

As the definition for greedy approach states, we need to find the best optimal solution
locally to figure out the global optimal solution. The inputs taken by the algorithm are
the graph G {V, E}, where V is the set of vertices and E is the set of edges. The shortest
path of graph G starting from one vertex returning to the same vertex is obtained as the
output.Algorithm

 Travelling salesman problem takes a graph G {V, E} as an input and declare another
graph as the output (say G’) which will record the path the salesman is going to take
from one node to another.
 The algorithm begins by sorting all the edges in the input graph G from the least
distance to the largest distance.
 The first edge selected is the edge with least distance, and one of the two vertices (say
A and B) being the origin node (say A).
 Then among the adjacent edges of the node other than the origin node (B), find the
least cost edge and add it onto the output graph.
 Continue the process with further nodes making sure there are no cycles in the output
graph and the path reaches back to the origin node A.
 However, if the origin is mentioned in the given problem, then the solution must always
start from that node only. Let us look at some example problems to understand this
better.

Examples
Consider the following graph with six cities and the distances between them −

From the given graph, since the origin is already mentioned, the solution must always
start from that node. Among the edges leading from A, A → B has the shortest distance.

Then, B → C has the shortest and only edge between, therefore it is included in the
output graph.

There’s only one edge between C → D, therefore it is added to the output graph.

There’s two outward edges from D. Even though, D → B has lower distance than D → E,
B is already visited once and it would form a cycle if added to the output graph.
Therefore, D → E is added into the output graph.

There’s only one edge from e, that is E → F. Therefore, it is added into the output graph.

Again, even though F → C has lower distance than F → A, F → A is added into the output
graph in order to avoid the cycle that would form and C is already visited once.
 The shortest path that originates and ends at A is A → B → C → D → E → F → A

The cost of the path is: 16 + 21 + 12 + 15 + 16 + 34 = 114.

Even though, the cost of path could be decreased if it originates from other nodes but
the question is not raised with respect to that.





Given a 2D matrix tsp[][], where each row has the array of distances
from that indexed city to all the other cities and -1 denotes that there
doesn’t exist a path between those two indexed cities. The task is to print
minimum cost in TSP cycle.
Examples:
Input:
tsp[][] = {{-1, 10, 15, 20},
{10, -1, 35, 25},
{15, 35, -1, 30},
{20, 25, 30, -1}};
Below is the given graph:

Output: 80
Explanation:
We are trying to find out the path/route with the minimum cost such that
our aim of visiting all cities once and return back to the source city is
achieved. The path through which we can achieve that, can be
represented as 1 -> 2 -> 4 -> 3 -> 1. Here, we started from city 1 and
ended on the same visiting all other cities once on our way. The cost of
our path/route is calculated as follows:
1 -> 2 = 10
2 -> 4 = 25
4 -> 3 = 30
3 -> 1 = 15
(All the costs are taken from the given 2D Array)
Hence, total cost = 10 + 25 + 30 + 15 = 80
Input:
tsp[][] = {{-1, 30, 25, 10},
{15, -1, 20, 40},
{10, 20, -1, 25},
{30, 10, 20, -1}};
Output: 50
We introduced Travelling Salesman Problem and discussed Naive and
Dynamic Programming Solutions for the problem in the previous post.
Both of the solutions are infeasible. In fact, there is no polynomial-time
solution available for this problem as the problem is a known NP-Hard
problem. There are approximate algorithms to solve the problem though.
This problem can be related to the Hamiltonian Cycle problem, in a way
that here we know a Hamiltonian cycle exists in the graph, but our job is
to find the cycle with minimum cost. Also, in a particular TSP graph, there
can be many hamiltonian cycles but we need to output only one that
satisfies our required aim of the problem.
Approach: This problem can be solved using Greedy Technique. Below
are the steps:
1. Create two primary data holders:
 A list that holds the indices of the cities in terms of the input matrix
of distances between cities.
 Result array which will have all cities that can be displayed out to
the console in any manner.
2. Perform traversal on the given adjacency matrix tsp[][] for all the city
and if the cost of the reaching any city from current city is less than
current cost the update the cost.
3. Generate the minimum path cycle using the above step and return
there minimum cost.
Time Complexity: O(N2*log2N)
Auxiliary Space: O(N)