Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Prerequisites
2.
Sample Examples
3.
Solution Approach
3.1.
Steps of algorithm
3.2.
Complexity Analysis
4.
Frequently Asked Questions 
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)

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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. 

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.

Previous article
Find the smallest range containing at least 1 element from given N ranges.
Next article
Minimize the sum of minimum and second minimum elements from all possible triplets
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass