AboutZlatko Expertise I can answer questions about C / C++ programming, software design, algorithms, and interprocess communication. I have access to Microsoft Visual Studio and gcc as my development platforms. I regret that I cannot answer questions about Turbo C/C++ graphics.
Experience I have been developing software professionally in C and C++ for UNIX and Microsoft Windows since 1991.
Education/Credentials I have a Bachelor of Applied Science in Computer Engineering from the University of Waterloo located in Waterloo, Ontario, Canada. I hold the IEEE Certified Software Development Professional designation and SUN Java Programmer and Java Developer credentials.
Question QUESTION: Hi Zlatko.
I'm doing some work at the moment, in which i've hit a brick wall. I'll post what i've done to begin with, to show what exactly i've done, and then explain where i'm stuck.
// You can assume no inputs will exceed these values:
#define MAX_BOXES 50
#define MAX_PARCELS 50
int main(void)
{
int numberOfBoxes, box, dataSet, ch, fp, i, y, j;
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], boxD[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", &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");
#
Number of boxes
box capacity
number of items
individual item weights
Ok so I need to pack a given data set as efficiently as possible, and i want to use a first fit decreasing algorithm to do so. ie. i want to try each item in the first box and if it doesnt fit there, try the next and so on. Then i want to assign the overflow (items that wont fit), into another variable.
I have tried many ways, but end up writing a huge amount of if statements, which obviously aren't very efficient.
Basically I would like some help on how i could implement a loop to optimally pack these items. I feel as though I know exactly what i need to do, but am having trouble expressing it in 'c'.
Apologies again for the long winded post, but i wanted to make it clear that i've attempted the problem and show what progress ive made.
Any help would be appreciated.
Thanks
ANSWER: Hello Derrick.
Thank you for your thought provoking question. I commend you for doing as much of your assignment as possible. My aim is to help you get your assignment done in an ethical way by Monday morning.
The quantity of C statements does not matter. What matters is the clarity of the code, and sometimes the efficiency of the algorithm. C is relatively low level. You will need many statements to get things done.
You seem to have a good grasp of the basic C operations but you are having difficulty thinking algorithmically. Your objective is to place a number of items into a number of boxes based on the box capacity. The code you showed me:
cannot do that. The code places all the items into boxA, and it does so a number of times.
The way to attack this problem is to imagine how you would do it yourself. Imagine a sorted collection of items and a set of boxes in front of you. I’d guess you’d pick up the largest item, then walk by all the boxes until you find one that can hold your item. Then you’d drop it in. You would not look further for another box for that item. You’d probably want to make a note of how much space is left in that box. Then you’d repeat the above operations until all of the items have been looked at. Any item that cannot be boxed is set aside somewhere else. Each item is examined only once. Do you notice the painful level of detail? Get used to thinking in details because computers don’t understand anything. This is exactly how you would do it in C but every artefact in your imagination has to be modeled as some kind of data in C and every move you make in your imagination corresponds to some operation on your data.
Your collection of items is already modeled as an array of numbers where the numbers represent weights. The weight is the only relevant attribute of an item, so that’s all we model.
What are the attributes of a box? It has a capacity, which will change as items are placed into it. It has parcels in it. You can represent the parcels in a box in the same way as you represent parcels out of the box. You can use an array of integers.
You have a number of boxes so the boxes can be collected in an array. You certainly would not want up to 50 (MAX_BOXES) variables of type boxA, boxB , etc.
If boxes are in an array, and each box has an array of items, you can see that you will need a two dimensional array to represent all these things. You will also need a capacity for each box, so you could use an array of capacities.
Your operation of taking an item and placing it into a box is modeled by putting an item into the box’s array, so you’d need to keep track of the next available spot in each box’s array. You could have an array for that too. You don’t actually have to remove the item from the source array. You do not always need a 1 to 1 correspondence between your program and reality.
Frankly, I find having all these arrays a little confusing, so I would gather all the relevant box attributes into a structure. Then I can think about the box as a unit, instead of a bunch of separate arrays. What about this?
typedef struct
{
int capacity; /* remaining capacity */
int parcelIndex; /* next available index in the parcels array */
int parcels[MAX_PARCELS]; /* array of parcel weights */
} Box;
Then we can model our set of boxes like this.
/* Here we have an array of boxes. Each box contains an array of parcels */
Box boxes[MAX_BOXES];
int boxIx; /* an index into the boxes array */
We can reuse this idea to create a storage location for items that cannot be boxed.
Box bigBox; /* This is a box of infinite capacity used to hold unassignable items */
Finally, we need to represent what is the next item to be examined.
int itemIx; /* index into the itemWeights array */
Now, all of our boxes are created on the stack, they contain random data. We need to initialize them.
/* basic initialization. Never forget to initialize your variables */
memset(boxes, 0, sizeof(boxes));
for (boxIx = 0; boxIx < numberOfBoxes; ++boxIx) boxes[boxIx].capacity = boxCapacity;
/* each item is looked at only once */
for(itemIx = 0; itemIx < numberOfItems; itemIx++)
{
…
Show me some ideas or at least some pseudo code, and I will give you feedback. I also have some suggestions about the working parts of the code which we can discuss once the boxing is done. I will check my e-mail today until about October 17, 3:00 PM Auckland time.
Best regards.
Zlatko
---------- FOLLOW-UP ----------
QUESTION: Hey, thanks a lot for the quick reply, and all of the help.
I think I understand what you're saying. Heres what I think.
I want to create a 2d box array, where each line represents an item, and each column represents a box? So it would be defined as:
int box[numberOfItems][numberOfBoxes]
I then want to cycle through each item and box possibility, ie if I had weights [1,2,3] and 3 boxes, I would want to try:
[1,1,1]
[1,1,2]
[1,2,1]
.
.
.
[3,2,3]
[3,3,3]
i played around this array above, but can only get it to go
[1,2,3]
[2,3,4]
[4,5,6]
etc
I may be on a completely wrong path here, but I see what I need to do, but have trouble implementing the loops.
If i didn't have an overflow of items, I can see that this would work, however there will be excess items, so I somehow need to allocate any overflow items to the bigBox variable as I loop through all of the combinations. Once I do this I can simply check, which combination results in the lowest bigBox number, hence this would be my optimum answer.
Any feedbeack on whether I'm on the right path or not would be appreciated.
Thanks
ANSWER: Derrick,
I can understand the use of int box[numberOfItems][numberOfBoxes].
You have an array of boxes, and each box has an array of items. But I don't understand how you are using the data structure. You say each column represents a box and each row represents an item. So does [1,1,1] indicate that box 1 and box 2 and box 3 each have an item of weight 1? Maybe, but I don't understand how the cycling through all combinations is consistent with the "first fit decreasing algorithm" which is a good algorithm for this job even if it's not optimal. Have you changed your mind about the algorithm?
If you go through all combinations, you will have to delete invalid combinations. For example, say you had items 1,2,3, then [1,1,1] is not even a valid combination.
I recommend you go with the initial first fit decreasing algorithm. If you don't like the idea of using the struct, we can go with more arrays.
Here is the start of the algorithm:
{
int boxIx; /* an index into the boxes array */
int itemIx; /* index into the itemWeights array */
int box[MAX_PARCELS][MAX_BOXES];
/* each item is looked at only once */
for(itemIx = 0; itemIx < numberOfItems; itemIx++)
{
/* find a box it fits in */
for(boxIx = 0; boxIx < numberOfBoxes; ++boxIx)
{
if (itemWeights[itemIx] <= capacities[boxIx])
{
/* Put item in the box */
box[???][boxIx] = itemWeights[itemIx];
break;
}
}
}
}
Notice i have ??? for one index when putting an item into the box. You need to keep track of the next available spot in the box array to hold an item. You need another array, with one element for each box, indicating the next available parcel location.
Create that array, initialize it, and use it, and update it. You will have something like this:
box[nextParcelSpot[boxIx]][boxIx] gets item
You see that you can nest the array indexes.
It's really less confusing to use the Box struct.
---------- FOLLOW-UP ----------
QUESTION: Thanks again for your reply.
I haven't learnt structs, so i'm not too sure how they work, however that last bit of code you wrote makes much more sense to me.
i am a bit confused where you wrote "if (itemWeights[itemIx] <= capacities[boxIx])" I don't see how the box capacity is an array, and what its index would be.
For the first index where you left ??? could i make an array called nextPacelSpot, that increments one each time we go through the loop, to check the next available spot.
ie if I wrote nextParcelSpot[boxIx++]?
Thanks again for your help
Answer You have to keep track of each box's capacity and decrease the capacity as you put items into the box. Each box will have its own capacity so you need as many capacities as you have boxes. If you have an array of boxes, you need an array of capacities.
for nextParcelSpot you need an array
int nextParcelSpot[MAX_BOXES];
To increment the array element, you do
nextParcelSpot[boxIx]++;
So your item goes into the next parcel spot for a particular box and that happens with:
box[nextParcelSpot[boxIx]][boxIx] = item;
nextParcelSpot[boxIx]++;
Keep at it.
Glad to help.
I'll be around Oct 18 from about 10 am to 2 pm your time if you have any more questions.
