Question

Create a C++ program with the algorithm.

Algorithm First Fit Terrance Tao or all elements i 1,2,3,...in do for all bins j = 1,2,3.... do . I objects i fits in bin j then pack object i in bin j. Break the top and pack the next object end if end for object i did not fit in any availahe bin then create new bin and Puck object i end if end for. First fit Decreasing Sort objects in decreasing order using coming Apply first fit merge sort i 2.?

Answer 1

Program to use first fit after merge sorting in decreasing order:

#include<bits/stdc++.h>
#include<stdlib.h>
using namespace std;
  
// Function to allocate memory to
// blocks as per First fit algorithm
void firstFit(int blockSize[], int m,
int processSize[], int n)
{
// Stores block id of the
// block allocated to a process
int allocation[n];
  
// Initially no block is assigned to any process
memset(allocation, -1, sizeof(allocation));
  
// pick each process and find suitable blocks
// according to its size ad assign to it
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (blockSize[j] >= processSize[i])
{
// allocate block j to p[i] process
allocation[i] = j;
  
// Reduce available memory in this block.
blockSize[j] -= processSize[i];
  
break;
}
}
}
  
cout << "\nProcess No.\tProcess Size\tBlock no.\n";
  
for (int i = 0; i < n; i++)
{
cout << " " << i+1 << "\t\t"
<< processSize[i] << "\t\t";
if (allocation[i] != -1)
cout << allocation[i] + 1;
else
{
//blocksize[i]={processSize[i]};
  
cout << allocation[i]+(m++)+2;
}
cout << endl;
}
}
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
  
/* create temp arrays */
int L[n1], R[n2];
  
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
  
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] >= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
  
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
  
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
  
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
  
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
  
merge(arr, l, m, r);
}
}
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
  
// Driver code
int main()
{
int blockSize[] = {100, 500, 200, 300, 600};
int arr[] = {212, 417, 112, 426,700,600,100};
int m = sizeof(blockSize) / sizeof(blockSize[0]);
int n = sizeof(arr) / sizeof(arr[0]);
int arr_size = sizeof(arr)/sizeof(arr[0]);
  
printf("Given array is \n");
printArray(arr, arr_size);
  
mergeSort(arr, 0, arr_size - 1);
  
printf("\nSorted array is \n");
printArray(arr, arr_size);
  
firstFit(blockSize, m, arr, n);
  
return 0 ;
}

**********************************************************************************************************************************************
Note that : Here blockSize is bin and processSize is object according to the algorithm given.