First fit bin packing help?

[wazz]

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:

#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

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

[Adak]

Welcome to the forum, Wazz!

A hint straighaway: Use (always), code tags (just highlight your code and in the text entering box, click on the ' # ' icon (right below the smilies pulldown menu). Edit: good, you added them!

That will then cause your code to be more readable, with better font types and background.

With these problems, it's a problem if you start code, before you have thoroughly thought through the algorithm.

You description sounds like you know the algorithm you need. The number of boxes you're allowed, is irrelevant as far as your program goes.

Can you plan out your possible combinations, and pack the boxes with any of the items, at any time?

In other words, if it's like a conveyor belt is passing the boxes by you, and you only have a few items at any time that you can pack into it, then you can't plan out your packing optimally.

If you *can* plan your packing, then you want to generate every combination of your items, and see if that combination of items can still fit into a box, to see which combo will be closest to the full value the box can hold.

Make sense? I don't see where your code is generating every possible combination of items.

[wazz]

Thanks for the fast reply

I gave that 'brute force' method a go, but it seemed far more complicated than just using a first fit decreasing algorithm, and for the data I tested, it still seemed to give me (most of the time) the correct order (I figured them out on paper first). So i figured because I couldn't really get my head around the former method, I'd stick to that...

So if I was to try every combination, I would need to loop through all of the item weights, and try each combination for however many boxes there were. But it seems that if I used this method, it would not be able to tell if there was an overflow?

Sorry I can't get my head around loops, let alone loops inside loops!
Anyway thanks for your help, I'll go and give it another shot

[Adak]

Thanks for the fast reply

Sorry I can't get my head around loops, let alone loops inside loops!
Anyway thanks for your help, I'll go and give it another shot

Brute force with all combinations will give you 100% optimization. Decreasing order will give you about 70% of optimum, in many tests with random values. The amount varies widely depending on the actual values of the items.

You don't care how many boxes you have, at first. You are looking for optimum combinations to fill any ONE box. Then you just repeat that, for the number of boxes you have.

If you haven't learned loops really well yet, I'd stick with what you have.

It's more complicated when you have to generate all the combinations, of course. Also, there is a considerable amount of time that will be needed to find every combination if you have up to 50 values.