C++ Program to Implement First Fit Decreasing for 1-D Objects and M Bins

This is a C++ Program to implement First Fit Decreasing for one dimensional objects and M bins. In simple terms this is bin packing algorithm for first fit technique.

Here is source code of the C++ Program to Implement First Fit Decreasing for 1-D Objects and M Bins. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <iostream>
  2. #include <time.h>
  3. #include <stdlib.h>
  4.  
  5. using namespace std;
  6.  
  7. void binPacking(int *a, int size, int n)
  8. {
  9.     int binCount = 0;
  10.     int binValues[n];
  11.     for (int i = 0; i < n; i++)
  12.         binValues[i] = size;
  13.  
  14.     for (int i = 0; i < n; i++)
  15.         for (int j = 0; j < n; j++)
  16.         {
  17.             if (binValues[j] - a[i] >= 0)
  18.             {
  19.                 binValues[j] -= a[i];
  20.                 break;
  21.             }
  22.         }
  23.  
  24.     for (int i = 0; i < n; i++)
  25.         if (binValues[i] != size)
  26.             binCount++;
  27.  
  28.     cout << "Number of bins required using first fit decreasing algorithm is:"
  29.             << binCount;
  30. }
  31.  
  32. int* sort(int *sequence, int n)
  33. {
  34.     // Bubble Sort descending order
  35.     for (int i = 0; i < n; i++)
  36.         for (int j = 0; j < n - 1; j++)
  37.             if (sequence[j] < sequence[j + 1])
  38.             {
  39.                 sequence[j] = sequence[j] + sequence[j + 1];
  40.                 sequence[j + 1] = sequence[j] - sequence[j + 1];
  41.                 sequence[j] = sequence[j] - sequence[j + 1];
  42.             }
  43.     return sequence;
  44. }
  45.  
  46. int main(int argc, char **argv)
  47. {
  48.     cout << "BIN - PACKING Algorithm 1D Objects(First Fit Decreasing)";
  49.     cout << "Enter the number of items in Set: ";
  50.  
  51.     int n;
  52.     cin >> n;
  53.     cout << "Enter " << n << " items:";
  54.     int a[n];
  55.     for (int i = 0; i < n; i++)
  56.         cin >> a[i];
  57.     cout << "Enter the bin size: ";
  58.     int size;
  59.     cin >> size;
  60.     int *sequence = sort(a, n);
  61.     binPacking(sequence, size, n);
  62. }

Output:

$ g++ FirstfitBinPacking.cpp
$ a.out
 
BIN - PACKING Algorithm 1D Objects(First Fit Decreasing)Enter the number of items in Set: 9
Enter 9 items:
4 
1
2
5
3
2
3
6
3
Enter the bin size: 6
Number of bins required using first fit decreasing algorithm is:5
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.