The Money Exchange Problem

[DrJones]

I enjoy wasting my time from time to time trying to solve problems with NP complex algorhytms in a polinomial time. These problems haven't algorhytms that solve them in polinomial time, of course.

One of them is "The Money Exchange Problem":

«We have a list with values in decreasing order, and we also have an endless amount of coins (first unsolvable problem) of each value. Find an algorhytm that, with an initial amount, returns the minimal number of coins needed to reach that amount.»

• This problem is unsolvable if not every amount is achievable with the list of values.
  
• The simplest algorhytm:
  

  code:

  ---

  
  
  
     - V: Array with values A, B, C, D... with A>B>C>D...
  
  
     - Amount: X
  
  
     - V[i] -> Value of the 'i' Position in the list.
  
  
     - T[i] -> Number of coins of the 'i' value;
  
  
     - For i=1 to End -> T[i]:=(X div V[i]);
  
  
                         X:=X-(T[i] * V[i]);
  
  
  

  ---

  
  Doesn't work for all lists of values. As an example -> X = 180, works with V = 100 50 25 10 5 2 1. (1 1 1 0 1 0 0)
  But not with V = 100 90 1. (1 0 80, instead of 0 2 0)
  

I made a "Fixer" algorhytm to use after the first one, but also has a round problem that need solve. I will post it after a break.

(To be Continued)

------------------

[This message has been edited by DrJones (edited 06-20-2003 08:16 AM).]

[Bicho the Inhaler]

Try PSPACE-complete problems. It can be frustrating, let me tell you. Nevertheless, there's quite a bit of research going into algorithms of PSPACE-complete problems. Anyway, more power to you, dude!

*Goes off to work on quantified Boolean formulas*

[DrJones]

This isn't a complete waste of time, as give you ideas you could use in other problems. Also, sciencist may be wrong.

And is funny!

This formula doesn't work to all values either, only those that satisfy the following:

For i:=1 to n-2 (where n is the lenght of V[i]) -> (V(i)-2V(i+1)) / V(i+2) is an integer;


And the algorhytm is:

code:

---

After the first algorhytm, we have T[i] with the total number of coins and V[i] with its values.





For i:=1 to n-2 do


   While (T(i+2)+V(i)) * V(i+2)) >= 2*V(B) do


      Begin


          T(i)-=1;


          T(i+1)+=2;


          T(i+2)+= (V(i)-2V(i+1)) / V(i+2);


      End;

---

Why T(i+1) increases by 2? Well, that's because decreasing T(i), we obtain enough cash to increase T(i+1) and remains V(i)-V(i+1), that increase T(i+2) in V(i)-V(i+1)/V(i+2). (as V(i)>V(i+1))

But, this increase if T(i+2) could be enough to make another coin in T(i+1), so:

code:

---

    if T(i+2)*V(i+2) >= V(i+1) then


       Begin


             T(i+1)+=1; 


             T(i+2)-= V(i+1)/V(i+2);


       End;

---

And, when do we decide it's better to decrease T(i)? When we predict that with the remaining (V(i)-V(i+1))/V(i+2) plus the present T(i+2) we will have enough to make 2 coins in T(i+1), which at the worst case will be the same number of coins that the ones we have when started. (Ex: 1 0 1 -> 0 2 0)

Let's Merge:

(T(i+2)+(V(i)-V(i+1)/V(i+2))) * V(i+2) = (T(i+2)+V(i))*V(i+2) - V(i+1)

code:

---

  If (T(i+2)+(V(i)) * V(i+2) >= 2V(i+1) then


     Begin


          T(i)-=1;


          T(i+1)+=2;


          T(i+2)+=(V(i)-2V(i+1))/V(i+2);


     End;

---

T(i+2) could decrease this time.

After all this write, I discovered that I was wrong with the election of decrease T(i), as I took always V(A)<=2V(B). So now I need to find a way to deal with both problems.

• Fix the decrease-chosing method, so it works too for every V(A)>2V(B).
  
• Find a solution to the round problem.
  

Wake up! I finished the class!

[This message has been edited by DrJones (edited 06-20-2003 12:39 PM).]