### Thread: Least Moves Algorithm

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2011
Posts
2
Rep Power
0

#### Least Moves Algorithm

My problem is this:

Suppose you have N urns that contain iron of a different weights (floating points). I need to cut iron from urns and throw it into other urns until each urn contains equal amounts of iron. I need an algorithm that tells me how much iron to take from which urn and which urn to put it into.

Of course this problem has several solutions; and I can think of some algorithms. But I am asking you for some good algortihms - hopefully an algortimh that gives the solution(s) which requires least moves.

I hope I've been clear enough, but let me, just to be sure, give an example:

Urn 1: 10 kg.
Urn 2: 0 kg.
Urn 3: 3 kg.
Urn 4: 7 kg.

A 'good' solution to this is:

Take 5 kg. from urn 1 and put into urn 2.
Take 2 kg. from urn 4 and put into urn 3.

I don't necessarily need exhaust algorithm that gives me all solutions. That would of course be best, but actually I only need one solution as long as it is optimal (least moves).

Thank you very much in advance.
2. Do you know how to determine which one has the fewest moves?

(I know an average case ~N/2 and worst case N-1 algorithm, but I don't know if it's optimal)
Last edited by requinix; July 7th, 2011 at 06:59 PM.
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2011
Posts
2
Rep Power
0
Originally Posted by requinix
Do you know how to determine which one has the fewest moves?

(I know an average case ~N/2 and worst case N-1 algorithm, but I don't know if it's optimal)
No, I wish I did.

My best bet is simply taking the urn with most iron and filling from this into the one with least, and constantly repeating this.

I would like to see your best algorithm, just for inspiration...
4. That's it, actually: take from the most and give to the least.
Code:
```3 1 4 1 5 9 2 6 5
^       ^
3 4 4 1 5 6 2 6 5
^   ^
3 4 4 4 5 3 2 6 5
^ ^
3 4 4 4 5 3 4 4 5
^       ^
4 4 4 4 4 3 4 4 5
^     ^
4 4 4 4 4 4 4 4 4```
Given M=the number of urns that need adjustment, the lower bound on the number of moves is ceil(M/2) (1 3 1 3) and the upper bound is M-1 (1 1 1 5).