Bin Packing Validation C++

Bin Packing problem description: Given an array of numbers, the goal is to group them into the minimum possible # of bins, but each bins items should not go above the fixed bin capacity of 100. Let us assume that array contents are already in sorted order.

However, in this lab, we are ONLY validating a possible solution - so, we need to get an array of numbers in one line, and another set of numbers in the next line to get the bin assignments for each number & check whether it is a valid solution. Here are a few sample inputs & outputs:

2 5 11 32 45 78 95 99 1 2 3 3 3 2 1 0 Valid 

The first line has the input numbers, Second line has the bin assignments. 2 goes to bin 1, 5 goes to bin 2, 11 goes to bin 3, So this solution uses 4 bins with the following totals in each bin: 99, 97, 83, 88. So the solution is valid!

 2 5 11 32 45 78 95 99 0 0 0 0 0 1 2 4 Bin 3 not used 

Bin index 4 is used & bin index 3 has been skipped - that is not valid.

2 5 11 32 45 78 95 99 0 0 0 0 0 1 1 2 Bin 1 total goes above 100 

A total of 78 and 95 go above 100. So, it is invalid.

2 5 11 32 45 78 95 99 0 0 11 0 0 1 2 3 Bin 11 out of range 

Bin 11 is out of range since there are only 8 items in the input! There is absolutely no need to use more than 8 bins.

2 5 32 45 78 95 99 111 0 0 0 0 0 1 2 3 Input item 111 out of range 

Since input item 111 is above 100 so it cannot be accommodated in any bin - it is invalid input.

Here is my code so far. I'm struggling with how to determine if the bin packing is valid or invalid if a bin is not used or if the total of numbers in a same bin is above 100. Please help me debug my code as soon as possible. Thank you and appreciate!

#include

#include

#include

using namespace std;

//let us assume we won't go over 100 numbers

const int MAXITEMS = 100;

int items[MAXITEMS], binAssignments[MAXITEMS];

int numItems=0; //stores actual # of items

const int BINCAPACITY = 100;

void validate() {

// WRITE YOUR CODE HERE

int b[8] = {0, 0, 0, 0, 0, 0, 0, 0};

for(int i=0; i

cin >> items[i];

cin >> binAssignments[i];

}

for(int i=0; i

if(items[i] > MAXITEMS){

cout << "Input item " << items[i] << " out of range" << endl;

return;

}

if(binAssignments[i] > i){

cout << "Bin " << binAssignments[i] << " out of range" << endl;

return;

}

b[binAssignments[i]] += items[i];

}

for(int i=0; i<8; i++){

if(b[i] > BINCAPACITY){

cout << "Bin " << i << " total goes above 100" << endl;

return;

}

}

}

int main() {

string line;

int numAssignments = 0;

//get all the items first.

getline(cin, line); //get one line of input

istringstream istr(line); //convert it to inputstringstream

//extract the numbers from the stream into the array

while (istr >> items[numItems])

numItems++;

//get bin assignments now.

getline(cin, line);

istringstream istr2(line);

while (istr2 >> binAssignments[numAssignments])

numAssignments++;

if (numItems != numAssignments) {

cout << "# of items and # of bin assignments mismatch.";

exit(1);

}

validate();

}