Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Need help developing an algorithm.. (http://www.go4expert.com/forums/help-developing-algorithm-t21893/)

Wildfire760 26Apr2010 05:12

Need help developing an algorithm..
 
Be prepared for a lengthy post...

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.

xpi0t0s 26Apr2010 13:50

Re: Need help developing an algorithm..
 
The problem could be that you are trying to solve it all in a single hit. This is not possible (which is why you've been thinking for over a week and not got anywhere). Split the problem down into simple steps and get each one working before moving onto the next.

I don't see why you need a linked list. Also you must need at least one array otherwise how would the orders "3 8 9 3 50 5 6" be represented?

The rules about split orders make it a lot easier than it would otherwise be. Essentially they are in a class of their own, so when you get to an order that is >40 you stop the previous processing and handle the split.

Trucks must be filled in order so that means you don't have to try to find an optimal solution. Just decide whether or not a truck is full or if there's a split needed, and move on to the next truck accordingly.

Code:

N=1
TruckN=0
get an order R
is R<=40?
yes:
  is TruckN+R>40?
  yes:
    need a new truck. Dispatch TruckN, N++, TruckN=R
  no:
    TruckN+=R
no:
  is TruckN==0?
    no:
      need a new truck for the split.  Dispatch TruckN, N++
  How many trucks do we need for this order?
  How many items per truck?  What if the order doesn't evenly divide by 40 (e.g. 100/3 -> 33, 33, 34)
  Dispatch trucks N, N+1, N+2,... with the relevant number of items
  Initialise next TruckN to 0


Wildfire760 26Apr2010 20:53

Re: Need help developing an algorithm..
 
Thanks for your response. A requirement of this program is no arrays are allowed. So when I am reading in the orders they are read into a queue using a linked list. Part of the challenge of this program is that we can't use the direct access of an array.

The part of this program that is driving me crazy is the even distribution. If you look at example two.
Which has the orders: 5 44 18 18 8 100 3.
If you look at in particular the orders 18 18 and 8. You will notice that they are split up as 18 in the first truck and 18 and 8 in the second. This is because the orders need to be distributed as evenly as possible and 18 and 26 is more even distribution then 36 and 8. So I really do need to find an optimal solution which I understand visually, but mentally I can't seem to find the algorithm to make this work.

Once again any help would be greatly appreciated.

xpi0t0s 26Apr2010 21:40

Re: Need help developing an algorithm..
 
Ah yes sorry I had missed that particular subtlety. OK, let's take some more example data. Here are some numbers I have for something else: 4 11 25 2 9 23 30. That's 104 in total, requiring 3 trucks (104/3=34r2). The most even packing I can find for this is 4+30+2=36, 25+9=34, 23+11=34, but this contradicts (1) that customer orders must be packed in order. 4+11+25=40; 2+9+23=34; 30 works for (1) but contradicts (3). So how would these orders be packed?

xpi0t0s 26Apr2010 21:43

Re: Need help developing an algorithm..
 
Also if you lop out the 5 44 100 from the example you used, leaving 18 18 8 3, how would that be packed? 18/18+8+3 is more even than 18+18/8+3, but a more even pack would be 18+8, 18+3.

Wildfire760 26Apr2010 22:00

Re: Need help developing an algorithm..
 
It needs to remain in customer order. So for 4 11 25 2 9 23 30. 4+11+25=40; 2+9+23=34; 30 is the way it has to be packed. Then with 18 18 8 3. It needs to be packed 18; 18 8 3 for a total of 29.

Here is more example data from the assignment:

Orders: 13 5 18 9 6 14 10

Truck 1: 13 5 18; 36 Total
Truck 2: 9 6 14 10; 39 Total

Orders: 2 39 8 50 29 5 20

Truck 1: 2
Truck 2: 39
Truck 3: 8
Truck 4: 25
Truck 5: 25
Truck 6: 29
Truck 7: 5 20; Total 25

I'm starting to literally have dreams about ways to solve this damn problem. The truck packing is just so weird. I don't know how to go about it.

xpi0t0s 26Apr2010 23:01

Re: Need help developing an algorithm..
 
OK this is not easy. Are you certain that the trucks *must* be packed as evenly as possible or would it be OK to pack them according to the algorithm I first suggested? i.e. bung the next order in the current van if there is space.

Here's one way to find a split point for two trucks:

13 / 5 18 9 6 14 10 =>13/62
13 5 / 18 9 6 14 10 => 18/57
13 5 18 / 9 6 14 10 => 36/39
13 5 18 9 / 6 14 10 => 45/30

Wildfire760 26Apr2010 23:10

Re: Need help developing an algorithm..
 
Yes i'm sure they need to be packed this way. This is why I have been struggling for days to no avail. Can you please explain your most current suggestion in more depth. I don't quite understand your method of finding the split points.

xpi0t0s 27Apr2010 02:04

Re: Need help developing an algorithm..
 
OK what I did here was to group the orders into two parts, one for each truck, and this is for two trucks. The first part is just the first number, and the second is the rest of the list. Add up both sides and record the difference (62-13). Move the split right one step, so the parts are now the first two orders and the rest of them. Add up both sides and record the difference (57-18). At the third step the difference is 39-36. At the fourth the difference is 45-30 which is worse than the previous difference, so the optimal split is at the third step.

For three trucks it's more tricky, basically a 2 dimensional search as you need two split points, using letters in place of numbers:
a/b/c d e f g
a/b c/d e f g
a/b c d/e f g
a/b c d e/f g
a/b c d e f/g
a b/c/d e f g
and so on. The most even layout won't necessarily be the first minimum as in the two truck scenario so you will need to search all possibilities and keep track of the lowest so far.

Four trucks will need three split points:
a/b/c/d e f g
a/b/c d/e f g
...etc

To code this up don't even try to figure it all out in advance. Get it working for 2 trucks, then 3, then 4, keeping an eye open for anything generic that might easily scale up to N trucks. Hopefully before you get too far you'll have an algorithm that scales to any number of trucks. It may be possible to perform a recursive algorithm where the depth is determined by the number of trucks. Also think about the possible limitations: if there is a limited number of trucks that you can send out, then obviously you don't need to solve it for that many.

A further complication is that orders that add up to <=40N won't necessarily only need N trucks. For example 35 35 8 adds up to 78, but that 8 won't fit into either truck and you will need a 3rd.

So this is why I queried the "must be spread evenly". This is a difficult requirement to fulfill and I'm still not convinced it's really required. It's difficult to code and has serious limitations. Follow this requirement back to source and determine where exactly it came from and why it is needed, and why the algorithm I first suggested won't satisfy your "customer". Point out that it contradicts the need to fulfil the requirement to fill trucks in the order specified and that if they were REALLY interested in optimising the truck loads they would be happy for a >40 order partial to be added to a truck that is already going somewhere else (so in other words it is already OK to send (a) one truck to multiple customers and (b) multiple trucks to one customer), and you may find your customer is happy to relax this. The best solution is for every truck out to be filled to capacity.

Relaxing this requirement also means a 35 35 8 would be splittable as 35+4 35+4, or 35+5 30+8 for a best solution of only two trucks on the road. 42 units (5+5+32) of empty space - more than a whole truck - is a lot of wastage for a design that is allegedly trying to minimise the number of trucks out.

Wildfire760 27Apr2010 02:15

Re: Need help developing an algorithm..
 
Thanks so much for your help. I am going to try to code all of this out.. Unfortunately, this program is an assignment for my intermediate cmp sci class. I don't think my teacher realized how ridiculous of a restriction he put on this program. I have cruised through all of my assignments up to this point, but I am honestly considering dropping out of my comp sci major over this. If real-life programming is going to be this stressful I don't know if I will make it to 30 without shooting myself.


All times are GMT +5.5. The time now is 10:44.