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
- Initialize the variable count = 0 to store the minimum number of bins required.
- Sort the weight arr[] in decreasing order to put the largest capacity element first into the bin.
- Initialize the multiset to store the empty spaces available in the bin in the current state.
- 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;
}

You can also try this code with Online C++ Compiler
Run Code
Output:
Minimum number of bins required is: 3

You can also try this code with Online C++ Compiler
Run Code
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.
Frequently Asked Questions
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.
Thank you for reading.
Until then, Keep Learning and Keep Coding.
