Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
July 7th, 2011, 03:03 PM
 Juliusbk
Registered User

Join Date: Jul 2011
Posts: 2
Time spent in forums: 40 m 59 sec
Reputation 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
July 7th, 2011, 06:55 PM
 requinix
Forgetful

Join Date: Mar 2007
Location: Washington, USA
Posts: 13,503
Time spent in forums: 5 Months 2 Weeks 2 Days 8 h 36 m 53 sec
Reputation Power: 9259
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
July 8th, 2011, 10:13 AM
 Juliusbk
Registered User

Join Date: Jul 2011
Posts: 2
Time spent in forums: 40 m 59 sec
Reputation Power: 0
Quote:
 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
July 8th, 2011, 02:33 PM
 requinix
Forgetful

Join Date: Mar 2007
Location: Washington, USA
Posts: 13,503
Time spent in forums: 5 Months 2 Weeks 2 Days 8 h 36 m 53 sec
Reputation Power: 9259
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).

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > Least Moves Algorithm