Hi, I'm new to programming, and am having a bit of trouble with a bin packing problem. I have found quite a bit of info on bin packing algorithms, but this problem differs slightly, as I have a limited number of boxes to use, so any excess items must be assigned to an unassigned variable.
I have the variables: Box Capacity, Number of items, Number of boxes and Individual itme weights. I want to try and pack the boxes as efficiently as I can, hence be left with the minimum unassigned weight.
So far I have written this:
Code:
#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
// You can assume no inputs will exceed these values:
#define MAX_BOXES 50
#define MAX_PARCELS 50
int main(void)
{
int numberOfBoxes[MAX_BOXES], box, dataSet, ch, fp, i, y;
int boxCapacity, numberOfItems, itemIndex, store;
int itemWeights[MAX_BOXES], swap, sum[MAX_PARCELS];
int boxA[MAX_PARCELS] = {0}, boxB[MAX_PARCELS] = {0}, boxC[MAX_PARCELS],
int boxE[MAX_PARCELS], boxF[MAX_PARCELS], uBox[MAX_PARCELS];
// User must input which data set they would like to use. This is stored in the variable dataSet
printf("Which data set? ");
scanf("%d", &dataSet);
// File is opened and read with fopen function and stored in the file pointer variable
fp = fopen("input2.txt", "r");
store = 0;
/* The # character is used to define each new data set, so a while loop is used to loop through the file and find the
data set that the user has requires */
while ((ch = fgetc(fp)) != EOF){
if (ch == '#'){
store++;
if (store == dataSet)
break;
}
}
/* The fscanf function is used to find the number of boxes, the box capacity, the number of items and the weight of
each individual item for the appropriate data set */
fscanf(fp, "%d", &numberOfBoxes);
printf("Number of Boxes: %d\n", numberOfBoxes);
fscanf(fp, "%d", &boxCapacity);
printf("Box Capacity: %d\n", boxCapacity);
fscanf(fp, "%d", &numberOfItems);
printf("Number of Items: %d\n", numberOfItems);
/* A for loop is used here to loop through the item weights data, and stores them in the itemWeights array */
printf("Item Weights: ");
for (itemIndex = 0; itemIndex < numberOfItems; itemIndex ++){
fscanf(fp, "%d" ,&itemWeights[itemIndex]);
printf("%d ", itemWeights[itemIndex]);
}
printf("\n");
/* This for loop loops through each integer in the array, and sorts it into descending order */
for(itemIndex = 0; itemIndex < numberOfItems; itemIndex++)
for(y = 0; y < numberOfItems-1; y++)
if(itemWeights[y] < itemWeights[y+1]) {
swap = itemWeights[y+1];
itemWeights[y+1] = itemWeights[y];
itemWeights[y] = swap;
}
printf("Item Weights Descending: ");
for (itemIndex = 0; itemIndex < numberOfItems; itemIndex ++){
printf("%d ", itemWeights[itemIndex]);
}
printf("\n");
And the output is
Code:
Number of Boxes: 3
Box Capacity: 150
Number of items: 10
Item Weights: 49 88 11 35 86 26 84 65 24 55
Item Weights Decreasing: 88 86 84 65 55 49 35 26 24 11
Sorry for a long winded post, but i figured i'd show what i've done so far
So I have read the data from the file, and have put the itemWeights array into decreasing order.
But now I'm stuck on how i could loop through the array and place each item in the first box it would fit into and place any overflow items in an 'unassigned box with infinite weight capacity'. I have tried a few options, but just end up haveing to write a ridiculous amount of if statements.
Im not asking for anyone to do this, but if someone could give me a few pointer as to how i'd start the loop, that would be awesome
Thanks