Algorithm is a small psuedocode in c++ Question 5: An instance of the bin packin

Question

Algorithm is a small psuedocode in c++

Question 5: An instance of the bin packing problem consists of a set, S, of objects, each with a size 0.0 < si 1.0, and your objective is to fit these objects into the fewest possible number of bins. Each bin has size equal to 1.0, so if you had two objects of sizes 0.3 and 0.65, you could put both in the same bin.

Part a: Give a greedy algorithm for the bin packing problem.

Part b: Give an example where your greedy algorithm does not find the optimal solution.

Explanation / Answer

#include<stdio.h>
void binPacking(int *a, int size, int n) {
int binCount = 1, i;
int s = size;
for (i = 0; i < n; i++) {
if (s - *(a + i) > 0) {
s -= *(a + i);
continue;
} else {
binCount++;
s = size;
i--;
}
}

printf("Number of bins required: %d", binCount);
}

int main(int argc, char **argv) {
printf("Enter the number of items in Set: ");
int n;
int a[n], i;
int size;
scanf("%d", &n);
printf("Enter %d items:", n);

for (i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("Enter the bin size: ");
scanf("%d", &size);
binPacking(a, size, n);
return 0;
}

#include<iostream>

using namespace std;

void binPacking(int *a, int size, int n)
{
int binCount = 1;
int s = size;
for (int i = 0; i < n; i++)
{
if (s - *(a + i) > 0)
{
s -= *(a + i);
continue;
}
else
{
binCount++;
s = size;
i--;
}
}

cout << "Number of bins required: " << binCount;
}

int main(int argc, char **argv)
{
cout << "BIN - PACKING Algorithm ";
cout << "Enter the number of items in Set: ";
int n;
cin >> n;
cout << "Enter " << n << " items:";
int a[n];
for (int i = 0; i < n; i++)
cin >> a[i];
cout << "Enter the bin size: ";
int size;
cin >> size;
binPacking(a, size, n);
}

file.open("test.bin", ios::in | ios::binary);
if(!file.is_open()) {
file.open("test.bin", ios::out | ios::binary);
int n = 3;
file.write(reinterpret_cast<char*>(&n), sizeof(n));
file.close();
file.open("test.bin", ios::in | ios::binary);
if(!file.is_open()) {
return -1;
}
}

// 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};
int c = 10;
int n = sizeof(weight) / sizeof(weight[0]);
cout << "Number of bins required in First Fit : "
<< firstFit(weight, n, c);
return 0;
}
Output:

Number of bins required in First Fit : 4
The above implementation of First Fit requires O(n2) time, but First Fit can be implemented in O(n Log n) time using Self-Balancing Binary Search Trees.

If M is the optimal number of bins, then First Fit never uses more than 1.7M bins. So First Fit is better than Next Fit in terms of upper bound on number of bins.

3. Best Fit:
The idea is to places the next item in the *tightest* spot. That is, put it in the bin so that smallest empty space is left.

// C++ program to find number of bins required using
// Best fit algorithm.
#include <bits/stdc++.h>
using namespace std;

// Returns number of bins required using best fit
// online algorithm
int bestFit(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 best bin that ca accomodate
// weight[i]
int j;

// Initialize minimum space left and index
// of best bin
int min = c+1, bi = 0;

for (j=0; j<res; j++)
{
if (bin_rem[j] >= weight[i] &&
bin_rem[j] - weight[i] < min)
{
bi = j;
min = bin_rem[j] - weight[i];
}
}

// If no bin could accommodate weight[i],
// create a new bin
if (min==c+1)
{
bin_rem[res] = c - weight[i];
res++;
}
else // Assign the item to best bin
bin_rem[bi] -= weight[i];
}
return res;
}

// Driver program
int main()
{
int weight[] = {2, 5, 4, 7, 1, 3, 8};
int c = 10;
int n = sizeof(weight) / sizeof(weight[0]);
cout << "Number of bins required in Best Fit : "
<< bestFit(weight, n, c);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.