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 itemsvoid 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 Codeint 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 Listfrom 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 functionitems = [4, 8, 1, 4, 2, 1]W = 10N = len(items)Â
bestFit(items, N, W) |
C#
// C# implementation of the approachusing 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 approachfunction 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);}Â
// Testlet items = [4, 8, 1, 4, 2, 1];let W = 10;let N = items.length;Â
// Function CallbestFit(items, N, W);Â
// This code is contributed by aadityaburujwale. |
Output:
2
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
