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

Output:

$ gcc BinPacking.c
$ ./a.out
 
BIN - PACKING Algorithm 1D Objects(First Fit Decreasing)
Enter the number of items in Set: 5
Enter 5 items: 12 23 34 45 56 
Enter the bin size: 50
Number of bins required using first fit decreasing algorithm is: 3

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

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

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 & technical discussions at Telegram SanfoundryClasses.