Need help solving a problem..

[Wildfire760]

I have been trying to solve this problem for days, and if I think about this anymore I might blow my brains out.

Anyways, I need help solving a smaller portion of a large assignment for my computer science course.

The program basically entails me creating a shipping manifest for a company. I am stuck trying to split up orders among trucks.

The restrictions placed on filling the trucks are as follows:
1.) Trucks must be filled with items in "Customer Order. That is Customer 1's orders must be filled first then Customer 2's then Customer 3's, etc.
2.)Each truck can hold a maxinum of 40 items.
3.) When multiple trucks are used, the orders must be distributed as evenly as possible between the trucks, keeping in mind that you must use as few trucks as possible and the orders must be filled in "Customer Order".
4.)No orders can be split, except for orders over 40.
-For orders over 40, split them as evenly as possible(for example: an order of 70
must be split 35 - 35 and order of 150 must be split 37 - 37 - 38 - 38).
-Trucks used for split orders must be used solely for that split order (They can not
hold any other Customer's orders.)

Examples of trucks being split properly:

Orders: 3 8 9 3 50 5 6
Truck 1 holds: 3 8 9 3 for a Total of 23.
Truck 2 holds: 25.
Truck 3 holds: 25.
Truck 4 holds 5 and 6 for a Total of 11.

Orders: 5 44 18 18 8 100 3
Truck 1 holds: 5
Truck 2 holds: 22
Truck 3 holds: 22
Truck 4 holds: 18
Truck 5 holds: 18 8 for a Total of 26.
Truck 6 holds: 33
Truck 7 holds: 33
Truck 8 holds: 34
Truck 9 holds: 3

Note: I can only build linked-lists using pointers. No arrays are allowed in this program.

If someone can please help me with this it would be greatly appreciated. Even if your help is so much as a nudge in the right direction. I have literally been thinking about this for over a week and I can not solve this problem.

[Banfa]

Well the initial thing to do is see if you can write down or actually catty out the process on paper.

It needs to be something like

INITIALISE TRUCK LIST TO EMPTY
CURRENT TRUCK = NEW EMPTY TRUCK
FOR EACH ORDER
    IF THE ORDER WILL FIT IN THE CURRENT TRUCK
        PUT THE ORDER IN THE CURRENT TRUCK
    ELSE
        PUT THE CURRENT TRUCK ON THE TRUCK LIST

        IF THE ORDER IS A SPLIT ORDER
            CALCULATE THE TRUCKS IN THE SPLIT ORDER
            PUT THE SPLIT ORDER TRUCKS ON THE TRUCK LIST
            CURRENT TRUCK = NEW EMPTY TRUCK
        ELSE
            CURRENT TRUCK = NEW EMPTY TRUCK
            PUT THE ORDER IN THE CURRENT TRUCK
        ENDIF
    ENDIF
END FOR EACH

IF THE CURRENT TRUCK IS NOT EMPTY
    PUT THE CURRENT TRUCK ON THE TRUCK LIST
ENDIF

PRINT TRUCK LIST

Also I think your second example is wrong I think trucks 4 and 5 should read

Truck 4 holds: 18 18 for a total of 36
Truck 5 holds: 8

Once you can do the process on paper you stand a better chance of being able to write a program that will do it.

[Wildfire760]

I have literally pages upon pages of work that has pretty much amounted to nothing. The problem is that the orders need to be distributed evenly not most efficiently.

So in example two the three orders you are referencing need to be split 18 and 18 8. Because 26 and 18 is a more even distribution then 18 18 and 8 or 36 and 8. This is the part of the program that is making my head want to explode..

[Banfa]

Sorry I had not fully realise the implication of rule 3. However I think something like this should work.

From the complete order list build a list of orders or work on. This sub list is bounded by any of the following conditions, the start and end of the main list, a split order. From the second example 18, 18, 8 would be a sub-list because it is bound at both ends by sub-lists.

Calculate the number of trucks required: (18 + 18 + 8) / 40 = 1.1 = 2 (because you can't have 0.1 of a truck)
Calculate the average load for each truck: (18 + 18 + 8) / 2 = 22

From the list fill the first truck until you are as close as possible to the average.
Truck 1: 18 because abs(22 - 18) < abs(22 - (18+18))

If there is 1 truck left put everything else into that truck
Truck 2: 18, 8

Else recalculate the new number of trucks and average.

If the number of trucks has not gone down by one then move up the stack of trucks until you can shift 1 load back into a previous truck. And restart.

Otherwise start filling the next truck.

I think you will need to do this recursively because I think there will always be possible load groupings that you will be unable to determine the correct layout for by a single pass. A Slightly tricking set of loads is

19, 20, 22, 24

I'll explain more if I get time later.

[abhimanipal]

@Banfa ...
When you calculate new number of trucks and load per truck why will you get a different value ?

[Banfa]

The problem is that there are lots of corner cases which is why you have to keep on recalculating number of trucks and expected average because you have to keep on adjusting your goal for what you have already done.

take this series of loads

10, 35, 15, 20, 10

On the first pass
Total load = 10 + 35 + 15 + 20 + 10 = 90
Trucks = 90 / 40 = 3 (rounded up)
Average Load = 90 / 3 = 30
Assign 10 to Truck 1, 35 wont fit into the truck so start pass 2

Pass 2
Total load = 35 + 15 + 20 + 10 = 80
Trucks = 80 / 40 = 2
Trucks has dropped by one calculation on track for 3 trucks
Average Load = 80 / 2 = 40
Assign 35 to truck 2, 15 wont fit in onto pass 3

Pass 3
Total load = 15 + 20 + 10 = 45
Trucks = 45 / 40 = 2 (rounded up)
Trucks has NOT dropped by one calculation not on track for 3 trucks however it is not possible to fit anything else into trucks 1 or 2 so we must actually be look for a 4 truck solution even though our initial estimate was 3
Average Load = 45 / 2 = 23 (rounding up)
Assign 15 to truck 3
Since abs(23 - 15) < abs(23 - (15 + 20)) do not assign 20 to truck 3
NOTE if at this point we were still using the average from step 1 of 30 then this would be Since abs(30 - 15) > abs(30 - (15 + 20)) do assign 20 to truck 3 result in a non-best fit of the last 3 loads into the last 2 trucks.

Pass 4
Total load = 20 + 10 = 30
Trucks = 30 / 40 = 1 (rounded up)
Trucks has dropped by one calculation on track for 4 trucks
Average Load = 30 / 1 = 30
Assign 20 and 10 to truck 4

No loads left, finish

Result

Truck 1: 10
Truck 2: 35
Truck 3: 15
Truck 4: 20 10

Taking the series (nearly) from my last post you get

19, 21, 22, 24

On the first pass
Total load = 19 + 21 + 22 + 24 = 86
Trucks = 86 / 40 = 3 (rounded up)
Average Load = 86 / 3 = 29 (rounded up)
Assign 19 to Truck 1
Since abs(29 - 19) < abs(29 - (19 + 21)) do not assign 21 to truck 1
Note however in this case 21 could fit in truck 1

pass 2
Total load = 21 + 22 + 24 = 67
Trucks = 67 / 40 = 2 (rounded up)
Trucks has dropped by one calculation on track for 3 trucks
Average Load = 67 / 2 = 34 (rounded up)
Assign 21 to Truck 1, 22 wont fit in onto pass 3

pass 3
Total load = 22 + 24 = 67
Trucks = 46 / 40 = 2 (rounded up)
Trucks has NOT dropped by one calculation NOT on track for 3 trucks, however note that there is an alternate arrangement for pass 1
Unwind pass 2 and redo pass 1

pass 1 again
Total load = 19 + 21 + 22 + 24 = 86
Trucks = 86 / 40 = 3 (rounded up)
Average Load = 86 / 3 = 29 (rounded up)
Assign 19 to Truck 1
Although abs(29 - 19) < abs(29 - (19 + 21)) assign 21 to truck 1 anyway because of the failure in pass 3 above.

pass 2
Total load = 22 + 24 = 46
Trucks = 46 / 40 = 2 (rounded up)
Trucks has dropped by one calculation on track for 3 trucks
Average Load = 46 / 2 = 23
Assign 22 to Truck 2, 24 wont fit in onto pass 3

pass 3
Total load = 24 = 24
Trucks = 24 / 40 = 1 (rounded up)
Trucks has dropped by one calculation on track for 3 trucks
Average Load = 24 / 1 = 24
Assign 24 to Truck 3

Not loads left Finish

Result
Truck 1: 19 21
Truck 2: 22
Truck 3: 24

You can see you keep recalculating to adjust your goals, if necessary you have to back track and try a different solution. What is clear is that the solution can not be done in a single pass. That is the correct truck for load N out of K for N < K can not be ascertained from loads 1 - N but is in fact dependent of all loads 1 - K.

[Wildfire760]

Thanks Banfa, I'm gonna give this a try. I appreciate all of your help.