Assume that you are given a set of items to be packed into bins. Each bin is mea
ID: 3684370 • Letter: A
Question
Assume that you are given a set of items to be packed into bins. Each bin is measured in height, weight, and length. The bins have the same standard dimensions, i.e. width, length and height values are uniform. There are n items with standard width and height, but with different heights listed as H=(h1,...,hn). It is also known that each item has a height at most the size of each bin so that it is guaranteed to fit into a bin. The goal is to place items into bins by using as few bins as possible. For this, the following greedy algorithm is given:
FirstFittingPlacement (H) {
for i = 1 to n
Place item i into the first bin it fits; // Place the item into the fitting bin with lowest index
end FirstFittingPlacement.
As an example, given a list of 6 items with heights H = {5, 4, 6, 8, 2, 3} and a standard bin size of 10 units, the given greedy algorithm will place the items into 4 bins as follows:
Bin1: [5, 4]
Bin2: [6, 2]
Bin3: [8]
Bin4: [3]
Whereas an optimal solution will place the same items into 3 bins as follows:
Bin1: [5, 4]
Bin2: [6, 3]
Bin3: [8, 2]
Therefore, the given greedy algorithm sometimes yields suboptimal solutions.
Give another example that will give a suboptimal solution for the given greedy algorithm. Please show your work. HINT: Height sizes may repeat.
Explanation / Answer
// C++ program to find number of bins required using First Fit algorithm.
#include <bits/stdc++.h>
using namespace std;
// Returns number of bins required using first fit
// online algorithm
int firstFit(int weight[], int n, int c)
{
// Initialize result (Count of bins)
int res = 0;
// Create an array to store remaining space in bins
// there can be at most n bins
int bin_rem[n];
// Place items one by one
for (int i=0; i<n; i++)
{
// Find the first bin that can accommodate
// weight[i]
int j;
for (j=0; j<res; j++)
{
if (bin_rem[j] >= weight[i])
{
bin_rem[j] = bin_rem[j] - weight[i];
break;
}
}
// If no bin could accommodate weight[i]
if (j==res)
{
bin_rem[res] = c - weight[i];
res++;
}
}
return res;
}
// Driver program
int main()
{
int weight[] = {2, 5, 4, 7, 1, 3, 8}; // gives output 4 while optimal is 3
int c = 10;
int n = sizeof(weight) / sizeof(weight[0]);
cout << "Number of bins required in First Fit : "
<< firstFit(weight, n, c);
return 0;
}
The above example also gives suboptimal solution for the given greedy algorithm
given a list of 7 items with heights H = {2, 5, 4, 7, 1, 3, 8} and a bin size of 10 units, the greedy algorithm will place the items into 4 bins as follows:
Bin1: [2, 5, 1]
Bin2: [4, 3]
Bin3: [7]
Bin4: [8]
first the height H goes into Bit 1, the 5 also goes into Bit 1. now no space is there for height 4 , so height 4 goes into Bit 2. Iterating over the array, 7 cannot fit into any Bin so it goes into new Bin 3.
Now 1 finds a space in Bit 1 nd 3 finds a space in Bit 2, but there is no space for height 8 , so a Bit 4 is formed which holds 8.
Whereas an optimal solution will place the same items into 3 bins as follows:
Bin1: [2, 8]
Bin2: [7, 3]
Bin3: [1, 5, 4]