Algorithm Help

[Ajapi]

Alright, I already passed a basic Algorithms course in school, but a friend who's taking it needs help with an exercise. I can't for the life of me figure out a simple way to do this... it is being made using a flowchart-generator, not a real programming language, so I can't access any advanced functions. This is the scenario:

You have to chose the cheapest, most efficient way to get somewhere. Now, assume the following price lists:

• 1 KM: $12
  
• 2 KM: $21
  
• 3 KM: $31
  
• 4 KM: $40
  
• 5 KM: $49
  
• 6 KM: $58
  
• 7 KM: $69
  
• 8 KM: $79
  
• 9 KM: $90
  
• 10KM: $101
  

So for example, the cheapest way to get a 15 KM trip would be to pay for a 3 KM trip and two 6 KM ones. What would the algorithm for this be like? I'm having a hard time with it..

Thanks in advance!

[Andre S. Veteran]

There seems to be no rule between KM and $ on your price list, so you need to sort them by km/price ratio and always use combinations made of the cheapest trips, reverting to higher priced one when adding a cheaper one would get you too far.

Maybe it's more complex than that, though. :unsure:

[Ajapi]

That's what I had in mind; using the cheapest KM/$ fares available in order to fulfill the whole trip. But I don't know how to create a loop that would check for the best combination :/

[MrA]

Seems easy enough. Here's how:

1. Calculate the cost/km for each km/$ pair, and sort them

2. Take the lowest cost/km and subtract as many kms as you can, keeping track.

3. Take the next lowest and repeat as per step 2

[Bookieass]

Well, the above logic run good

But I guess this will also do!!!

Hope you would appreciate :)

Try this

Step 1.

Factor your distance to travel into prime factors

Step 2.

Suppose, u want to travel 15kms then after factorizing you will able to get it as product of 3*5

i.e 5 times three, no as from your table of KM's to Cost i c that rate even km's is slightly less than the that of odd ones.

So form even numbers of the factorzing number as much as possible

for 15km's it would be (3+3)+(3+3) + 3

which would result into your required least cost!!! :)

Hope it helps, plz feel free to comment

[HeartsOfWar]

Seems easy enough. Here's how:

1. Calculate the cost/km for each km/$ pair, and sort them

2. Take the lowest cost/km and subtract as many kms as you can, keeping track.

3. Take the next lowest and repeat as per step 2

(Y)

[MrA]

Seems easy enough. Here's how:

1. Calculate the cost/km for each km/$ pair, and sort them

2. Take the lowest cost/km and subtract as many kms as you can, keeping track.

3. Take the next lowest and repeat as per step 2

(Y)

:no:

Sorry, but my algorithm doesn't work, at least not in the general case.

Consider the following:

10km - $10 = $1/km

1km - $5 = $5/km

8km - 9$ = $1.125/km

Now say you want to go 16km. According to the algorithm I gave, you would take 1 - 10km and 6 - 1km, which would add up to $40. Now, you could take 2 - 8km which would give you $18.

[Argote]

Looks like you'd need a Branch & Bound tree where you will break of if you have already exceeded the minimum cost so far or the distance you need to travel.

[Andre S. Veteran]

If you don't need the most efficient algorithm... and want to save yourself a headache...

Start by computing a possible path. Any one. That will cost a certain amount. Save that amount as the cheapest known path.

Now go through all possible combinations. This might be prohibitingly expensive, but you can break out of any calculation as soon as it exceeds the cheapest known path, and avoid equivalent permutations (2x8kms + 3x1km == 3x1km + 2x8kms). When a cheaper path is found, update your cheapest known path variable.

When all possibilities have been examined, you have the cheapest path!

Of course, given a long list of prices, this might take a while. For 10 prices, for instance, the worst case scenario will require to evaluate 92 378 possibilities, and that's if you avoid equivalent permutations. For 20 prices, worst case scenario is 68 923 264 410 possibilities avoiding equivalent permutations.

If you don't bother avoiding equivalent permutations (consider order important), then worst case scenario is n^n. :p

EDIT: actually the number of possiblities is MUCH lower if you only consider those that make up the required number of kilometers.

Edited November 21, 2008 by Dr_Asik

[Astra.Xtreme]

Maybe a possible way to start would be to assign each of the pricings a variable.

Read in the trip length and run it through a loop that would break it down starting with 10 and down to 1.

Probably would if/else using modulus (remainder) to make sure you get integer values. (If that even makes sense?)

Then obviously once you have the pricing choices, calculate out the total price using the variables.

My brain is drained from finals, so I don't know if any of that makes sense. Maybe you'll get some sort of idea from it.

[JamesCherrill]

With the data supplied, you can reduce the problem size by ignoring the 9 and 10 km options completely (9 km > 5 + 4 and 10 > 6+4 or 2*5, so they will never figure in a cheapest solution))

[Argote]

:p

EDIT: actually the number of possiblities is MUCH lower if you only consider those that make up the required number of kilometers.

Or it could be much higher if the list of prices stayed like the one the OP listed but the distance you want to cover is much higher (i.e. 5000 km).

In that regard, you could use the lowest price per kilometer fare until you are within the distance of the longest trip available.

[Ajapi]

Guys, really.. thanks a lot for the input! I'm trying to code this into C++ and I must say, having fun at it. If I ever finish it, I'll post the code up :p

[Andre S. Veteran]

I would be curious to see the code, indeed.

[AhmedAbdullah]

well, i found a good one that might work,

here it's simply

before startl, naming:

km = KM trip

cost(int km) //a method that calculate the least cost combination of trips

{

if ( km <=0 ) invalid trip

else if ( 1 <= km < 9 )

use the mentioned prices. i.e. 1 km => $12, 8 Km => $79

else //(km >= 9)

(km/5) * cost(km/2) + cost(cost%2)

}

notice that the km/2 and km%2 are integers i.e 9/2 = 4 and 9%2 = 1

I know this is NOT an algorithm exactly and not an complete code, it is in between and it must be done "Recursively"

[Andareed]

This is the unbounded knapsack problem (see http://en.wikipedia.org/wiki/Knapsack_problem). The greedy algorithm won't necessarily give you the optimal solution. You should take a look at a dynamic programming solution.

[AhmedAbdullah]

This is the unbounded knapsack problem (see http://en.wikipedia.org/wiki/Knapsack_problem). The greedy algorithm won't necessarily give you the optimal solution. You should take a look at a dynamic programming solution.

OMG! this is exactly what I did :-) even though I didn't know about that !!!

We can define A(j,Y) recursively as follows:

A(0, Y) = 0 
A(j, 0) = 0 
A(j, Y) = A(j − 1, Y)  if wj > Y 
A(j, Y) = max { A(j − 1, Y),  pj + A(j − 1, Y − wj) }  if wj ≤ Y. 
The solution can then be found by calculating A(n, W). To do this efficiently we can use a table to store previous computations. This solution will therefore run in O(nW) time and O(nW) space, though with some slight modifications we can reduce the space complexity to O(W).

Good luck guys