1.
Introduction
1.1.
Prerequisites
2.
Sample Examples
3.
Solution Approach
3.1.
Steps of algorithm
3.2.
Complexity Analysis
4.
4.1.
What is a best-fit algorithm?
4.2.
What is a comparator class in C++?
4.3.
What is multiset Data Strcutrue?
4.4.
What are the different functions of multiset in c++?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Find a minimum number of bins to place N items(using the best-fit algorithm)

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## Introduction

We are given N items in the arr[] and an integer C which represents the capacity of the bin(all bins have the same capacity); arr [] contains the weight of each item. We need to put all the items into the bins, our main task is to calculate the minimum number of bins required. It is always guaranteed that the size of bin C will always be greater than the maximum weight of N items.

### Prerequisites

We are going to solve this problem using a best-fit algorithm, so knowledge of multiset is needed to proceed further. To study the multiset, you can refer to this link

## Sample Examples

Example 1:

``````Input: arr[] = {4,8,1,4,2,1}, C = 8

Output: The minimum number of bins required is: 3

Explanation:
The first bin will contain {4, 4}.
The second bin will contain {8}.
The third bin will contain {1,1,2}.
Therefore the minimum number of bins required is 3. ``````

Example 2:

``````Input: arr[] = {9,8,5,6,7}, C = 15

Output: The minimum number of bins required is: 3

Explanation:
The first bin will contain {9,5}.
The second bin will contain {8,6}.
The third bin will contain {7}.
Therefore the minimum number of bins required is 3. ``````
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Solution Approach

We will solve this problem using the best-fit algorithm. The algorithm states that we will put the next element in the next smallest space present in the bin just greater than the weight of the current element. If there is no such space, we will take the new bin and put the current element into this new bin. We will use the multiset to store the empty spaces in the bin.

### Steps of algorithm

1. Initialize the variable count = 0 to store the minimum number of bins required.
2. Sort the weight arr[] in decreasing order to put the largest capacity element first into the bin.
3. Initialize the multiset to store the empty spaces available in the bin in the current state.
4. Traverse the weight arr[], and for every element do the following:
• If space exists in the multiset greater than or equal to the arr[i], let's say it 'space.'
• Remove 'space' from the multiset, and insert 'space - arr[i]' into the multiset. It means that we have inserted the current item into that available space.
• If no space is available, we will insert the new item into the new bin, increase the count by 1, and insert C-arr[i](remaining space) into the multiset.

5. Finally, print the count, which will denote the minimum number of bins required to put all the items.

``````// program to understand the best-fit algorithm
#include<bits/stdc++.h>
using namespace std;

// utitlity function to find the minimum number of bins
// using the best-fit algorithm
int minimumBins(vector<int>&arr, int C){
// size of the given arr[]
int n = arr.size();

// initializing the multiset to accomdate the free space
multiset<int>mp;

// declaring the count variable, to keep the check of number of bins requrired
int count = 0;
for(int i=0;i<n;i++){

// checking if the avaiable space is
// equal to the current element
auto it = mp.find(arr[i]);

// if empty space avaiable in the multiset
// is itself equal to the current element
if(it!=mp.end()){
mp.erase(it);
} else{
// checking if the avaiable space in the
// multiset is greater than current element or not
auto it1 = mp.upper_bound(arr[i]);
//if present
if(it1!=mp.end()){
// insert the next avaiable space after inserting the current element
mp.insert(*it1 - arr[i]);
// remove the space that is used
mp.erase(it1);
}else{
// if there is no avaiable space, create the new bin
// and hence increase the count
count++;
// and insert the remaining space into the multiset,
// after creating the new bin
mp.insert(C - arr[i]);
}
}
}
return count;
}
int main(){
vector<int>arr = {4,8,1,4,2,1};
int C = 8;
cout << "Minimum number of bins required are : " << minimumBins(arr, C) << endl;
}``````

Output:

``Minimum number of bins required is: 3 ``

### Complexity Analysis

Time Complexity: O(N + NLogN)

Explanation: O(N) for traversing the array and(NlogN) for maintaining the multiset.

Space Complexity: O(N)

Explanation: We are using the multiset data structure, so this extra space is used.

#### What is a best-fit algorithm?

Best Fit is a memory management strategy that allocates the smallest free partition that matches the requesting process's requirements.

#### What is a comparator class in C++?

The objects of user-defined classes are compared using Comparator Classes. To create a generic function, start with a template, and then add containers to make the function more generic. This allows for data comparisons.

#### What is multiset Data Strcutrue?

A MultiSet is a data structure that holds and manipulates an unordered collection of repeatable components. It is realized as a Maple object. Create, update, query, and otherwise interact with one or more MultiSet objects using the method exports of a MultiSet.

#### What are the different functions of multiset in c++?

Multisets are associative containers that are similar to sets but allow several items to have the same values. The following are some basic multiset functions:

• begin() â€“ Returns an iterator to the multiset's initial element.
• end() â€“ Returns an iterator to the theoretical element that comes after the multiset's last element.
• size() â€“ Returns the multiset's size in elements.
• max size() â€“ Returns the multiset's maximum number of entries.
• empty() - checks if the multiset is empty.

## Conclusion

In this article, we discussed the problem of finding a minimum number of bins to place N items(using the best-fit algorithm). If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free!

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, System Design, JavaScript, etc. Enroll in our courses, refer to the mock test and problems available, interview puzzles, and look at the interview bundle and interview experiences for placement preparations.