Question

In the bin packing problem, items of different weights (or sizes) must be packed into a finite number of bins each with the capacity C in a way that minimizes the number of bins used. The decision version of the bin packing problem (deciding if objects will fit into <= k bins) is NP-complete. There is no known polynomial time algorithm to solve the optimization version of the bin packing problem. In this practice problem you will be examining three greedy approximation algorithms to solve the bin packing problem. 

- First-Fit: Put each item as you come to it into the first (earliest opened) bin into which it fits. If there is no available bin then open a new bin.
- First-Fit-Decreasing: First sort the items in decreasing order by size, then use First-Fit on the resulting list.
- Best Fit: Place the items in the order in which they arrive. Place the next item into the bin which will leave the least room left over after the item is placed in the bin. If it does not fit in any bin, start a new bin.

a) Give pseudo code and the running time for each of the approximation algorithms.

b) Implement the algorithms in C++. Your program named binpack should read in a text file named bin.txt with multiple test cases as explained below and output to the terminal the number of bins each algorithm calculated for each test case. Submit a README file

Example bin.txt: The first line is the number of test cases, followed by the capacity of bins for that test case, the number of items and then the weight of each item. You can assume that the weight of an item does not exceed the capacity of a bin for that problem.
3
10
6
5 10 2 5 4 4
10
20
4 4 4 4 4 4 4 4 4 4 6 6 6 6 6 6 6 6 6 6
10
4
3 8 2 7

Sample output:
Test Case 1 First Fit: 4, First Fit Decreasing: 3, Best Fit: 4
Test Case 2 First Fit: 15, First Fit Decreasing: 10, Best Fit: 15
Test Case 2 First Fit: 3, First Fit Decreasing: 2, Best Fit: 2

c) Randomly generate at least 20 bin packing instances. Summarize the results for each algorithm. Which algorithm performs better? How often? Note: Submit a description of how the inputs were generated not the code used to produce the random inputs.

Answer 1

ANSWER:

//main.cpp
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include "mergesort.h"

#define CAPACITY 100
#define MAX_ITEM_NUM 10000
#define MAX_WEIGHT 100
#define INTERVAL 1000

using std::cout;
using std::cin;
using std::endl;
using std::ifstream;
using std::string;
using std::vector;

int firstFit(int capacity, vector<int> weights);
void timeRandom(int sort);

int main()
{
// open bin file
ifstream data;
string path = "bin.txt";
data.open(path.c_str());

vector<int> itemWeightVector;

int testCaseCount = 0;
int testCaseNum = 0;
int capacity = 0;
int itemNum = 0;
int itemWeight = 0;

// get number of test cases
while (data >> testCaseNum)
{
//cout << "testCaseNum: " << testCaseNum << endl;
// for each test case
for (int i = 0; i < testCaseNum; i++)
{
// get capacity of bins
data >> capacity;
//cout << "capacity: " << capacity << endl;

// get number of items
data >> itemNum;
//cout << "itemNum: " << itemNum << endl;

// for each item
for (int i = 0; i < itemNum; i++)
{
// get the weight of each item
data >> itemWeight;
itemWeightVector.push_back(itemWeight);
//cout << itemWeight << " ";
}
//cout << endl;

// run first-fit
int ff = firstFit(capacity, itemWeightVector);

// reverse sort weights of each item
mergesort(itemWeightVector, 0, itemWeightVector.size() - 1);

/*
for (int i = 0; i < itemWeightVector.size(); i++)
{
cout << "itemWeightVector: " << itemWeightVector[i] << endl;;
}
*/

// run first-fit-decreasing
int ffd = firstFit(capacity, itemWeightVector);

// output results
cout << "Test Case " << testCaseCount << " First Fit: " << ff << " - First Fit Decreasing: " << ffd << endl;

// clear vectors for next test case
itemWeightVector.clear();
testCaseCount += 1;
}
}

timeRandom(0);
cout << endl;
timeRandom(1);
}

int firstFit(int capacity, vector<int> weights)
{
vector<int> bins;
bins.push_back(capacity);

// for all items in weights vector
for (int i = 0; i < weights.size(); i++)
{
// boolean switch
// 1 if item fit into existing bin, 0 if not
int fit = 0;

// compare with all bins
for (int j = 0; j < bins.size(); j++)
{
// if item weight is less than space available in bin j
if (weights[i] <= bins[j])
{
//cout << "item " << i << " fits into bin " << j << endl;
// add item to bin j
bins[j] -= weights[i];
fit = 1;
break;
}
}
//cout << "fit: " << fit << endl;
if (fit == 0)
{
//cout << "adding bin" << endl;
bins.push_back(capacity);
bins[bins.size() - 1] -= weights[i];
}
}
//cout << "bin size: " << bins.size() << endl;
return bins.size();
}

void timeRandom(int sort)
{
// seed random generator
srand(time(NULL));

vector<int> itemWeightVector;

int n = 0;

cout << "n" << '\t' << "runtime (s)" << '\t' << "bins" << endl;
while (n < MAX_ITEM_NUM)
{
for (int i = 0; i <= n; i++)
{
itemWeightVector.push_back(rand() % MAX_WEIGHT);
//cout << "itemWeightVector: " << itemWeightVector[i] << endl;
}

//return 1;

clock_t start;
clock_t end;
start = clock();

if (sort == 1)
{
// reverse sort weights of each item
mergesort(itemWeightVector, 0, itemWeightVector.size() - 1);
}

// run first-fit
int ff = firstFit(CAPACITY, itemWeightVector);

// calculate and output array size n and time in seconds
end = clock();
double diff = ((double)end - (double)start);
double runtime = diff / (double) CLOCKS_PER_SEC;

cout << n << '\t' << runtime << '\t' << ff << endl;

// increment n
n += INTERVAL;

// reset item weight vector
itemWeightVector.clear();
}
}
--------------------------------------------------------------------------------------------
//mergesort.cpp
#include "mergesort.h"
#include <fstream>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

using std::ifstream;
using std::ofstream;
using std::string;
using std::vector;
using std::cout;
using std::endl;

// list of integers via the merge sort algorithm
void merge(vector<int>&list, int p, int q, int r)
{

int n = q - p + 1;
int m = r - q;

int L[n];
int R[m];

for (int i = 0; i < n; i++)
{
L[i] = list[p + i];
}

for (int j = 0; j < m; j++)
{
R[j] = list[q + 1 + j];
}

int i = 0;
int j = 0;
int k = p;

while (i < n && j < m)
{
if (L[i] >= R[j])
{
list[k] = L[i];
i = i + 1;

}

else
{
list[k] = R[j];
j = j + 1;
}

k += 1;
}

while (i < n)
{
list[k] = L[i];
i += 1;
k += 1;
}

while (j < m)
{
list[k] = R[j];
j += 1;
k += 1;
}
}

// recursively sorts a list of integers via the merge sort algorithm
void mergesort(vector<int>& list, int p, int r)
{
if (p < r)
{
int q = (p + r) / 2;

mergesort(list, p, q);

mergesort(list, q + 1, r);

merge(list, p, q, r);
}
}

----------------------------------------------------------------------------------------
//mergesort.h
#ifndef MERGESORT
#define MERGESORT

#include <fstream>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

using std::ifstream;
using std::ofstream;
using std::string;
using std::vector;
using std::cout;
using std::endl;

void merge(vector<int>&list, int p, int q, int r);
void mergesort(vector<int>&list, int p, int r);

#endif