Given an array weight[] consisting of weights of N items and a positive integer C representing the capacity of each bin, the task is to find the minimum number of bins required such that all items are assigned to one of the bins.
Examples:
Input: weight[] = {4, 8, 1, 4, 2, 1}, C = 10
Output: 2
Explanation: The minimum number of bins required to accommodate all items is 2.
The first bin contains the items with weights {4, 4, 2}.
The second bin contains the items with weights {8, 1, 1}.Input: weight[] = {9, 8, 2, 2, 5, 4}, C = 10
Output: 4
Approach: The given problem can be solved by using the best-fit algorithm. The idea is to place the next item in the bin, where the smallest empty space is left. Follow the steps below to solve the problem:
- Initialize a variable, say count as 0 that stores the minimum number of bins required.
- Sort the given array weight[] in decreasing order.
- Initialize a multiset, say M to store the empty spaces left in the occupied bins presently.
- Traverse the array weight[] and for each element perform the following steps:
- If there exists the smallest empty space which is at least arr[i] is present in the M, then erase that space from M and insert the remaining free space to M.
- Otherwise, increment the count by 1 and insert the empty space of the new bin in M.
- After completing the above steps, print the value of count as the minimum number of bins required.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum number // of bins required to fill all items void bestFit( int arr[], int n, int W) { // Stores the required number // of bins int count = 0; // Sort the array in decreasing order sort(arr, arr + n, greater< int >()); // Stores the empty spaces in // existing bins multiset< int > M; // Traverse the given array for ( int i = 0; i < n; i++) { // Check if exact space is // present in the set M auto x = M.find(arr[i]); // Store the position of the // upperbound of arr[i] in M auto y = M.upper_bound(arr[i]); // If arr[i] is present, then // use this space and erase it // from the map M if (x != M.end()) { M.erase(x); } // If upper bound of arr[i] is // present, use this space and // insert the left space else if (y != M.end()) { M.insert(*y - arr[i]); M.erase(y); } // Otherwise, increment the count // of bins and insert the // empty space in M else { count++; M.insert(W - arr[i]); } } // Print the result cout << count; } // Driver Code int main() { int items[] = { 4, 8, 1, 4, 2, 1 }; int W = 10; int N = sizeof (items) / sizeof (items[0]); // Function Call bestFit(items, N, W); return 0; } |
Java
import java.util.*; public class Main { // Function to find the minimum number // of bins required to fill all items public static void bestFit( int [] arr, int n, int W) { // Stores the required number // of bins int count = 0 ; // Sort the array in decreasing order Arrays.sort(arr); for ( int i= 0 ;i<arr.length/ 2 ;i++){ int temp = arr[i]; arr[i] = arr[arr.length-i- 1 ]; arr[arr.length-i- 1 ] = temp; } // Stores the empty spaces in // existing bins TreeSet<Integer> M = new TreeSet<>(); // Traverse the given array for ( int i = 0 ; i < n; i++) { // Check if exact space is // present in the set M Integer x = M.floor(arr[i]); // Store the position of the // upperbound of arr[i] in M Integer y = M.higher(arr[i]); // If arr[i] is present, then // use this space and erase it // from the map M if (x != null ) { M.remove(x); } // If upper bound of arr[i] is // present, use this space and // insert the left space else if (y != null ) { M.add(y - arr[i]); M.remove(y); } // Otherwise, increment the count // of bins and insert the // empty space in M else { count++; M.add(W - arr[i]); } } // Print the result System.out.println(count); } public static void main(String[] args) { int [] items = { 4 , 8 , 1 , 4 , 2 , 1 }; int W = 10 ; int N = items.length; // Function Call bestFit(items, N, W); } } // This code is contributed by aadityaburujwale. |
Python3
from typing import List from collections import defaultdict def bestFit(arr: List [ int ], n: int , W: int ) - > None : # Stores the required number # of bins count = 0 # Sort the array in decreasing order arr.sort(reverse = True ) # Stores the empty spaces in # existing bins M = defaultdict( int ) # Traverse the given array for i in range (n): # Check if exact space is # present in the dictionary M if arr[i] in M: del M[arr[i]] # If upper bound of arr[i] is # present, use this space and # insert the left space elif arr[i] + 1 in M: M[M[arr[i] + 1 ] - arr[i]] = M[arr[i] + 1 ] del M[arr[i] + 1 ] # Otherwise, increment the count # of bins and insert the # empty space in M else : count + = 1 M[W - arr[i]] = W # Print the result print (count) # Test the function items = [ 4 , 8 , 1 , 4 , 2 , 1 ] W = 10 N = len (items) bestFit(items, N, W) |
C#
// C# implementation of the approach using System; using System.Linq; using System.Collections.Generic; public class GFG { // Function to find the minimum number // of bins required to fill all items public static void bestFit( int [] arr, int n, int W) { // Stores the required number // of bins int count = 0; // Sort the array in decreasing order Array.Sort(arr); arr = arr.Reverse().ToArray(); // Stores the empty spaces in // existing bins SortedSet< int > M = new SortedSet< int >(); // Traverse the given array for ( int i = 0; i < n; i++) { // Check if exact space is // present in the set M int x = M.GetViewBetween( int .MinValue, arr[i]).LastOrDefault(); // Store the position of the // upperbound of arr[i] in M int y = M.GetViewBetween(arr[i], int .MaxValue).FirstOrDefault(); // If arr[i] is present, then // use this space and erase it // from the map M if (x != 0) { M.Remove(x); } // If upper bound of arr[i] is // present, use this space and // insert the left space else if (y != 0) { M.Add(y - arr[i]); M.Remove(y); } // Otherwise, increment the count // of bins and insert the // empty space in M else { count++; M.Add(W - arr[i]); } } // Print the result Console.WriteLine(count); } public static void Main( string [] args) { int [] items = { 4, 8, 1, 4, 2, 1 }; int W = 10; int N = items.Length; // Function Call bestFit(items, N, W); } } // This code is contributed by phasing17 |
Javascript
// JavaScript program for the above approach function bestFit(arr, n, W) { // Stores the required number // of bins let count = -1; // Sort the array in decreasing order arr.sort((a, b) => b - a); // Stores the empty spaces in // existing bins let M = new Set(); // Traverse the given array for (let i = 0; i < n; i++) { // Check if exact space is // present in the set M if (M.has(arr[i])) { M. delete (arr[i]); } else { // Find the minimum element // greater than arr[i] in M let y = Array.from(M).find(x => x > arr[i]); // If upper bound of arr[i] is // present, use this space and // insert the left space if (y) { M.add(y - arr[i]); M. delete (y); } // Otherwise, increment the count // of bins and insert the // empty space in M else { count++; M.add(W - arr[i]); } } } // Print the result console.log(count); } // Test let items = [4, 8, 1, 4, 2, 1]; let W = 10; let N = items.length; // Function Call bestFit(items, N, W); // This code is contributed by aadityaburujwale. |
2
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!