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

    Join Date
    Jul 2011
    Posts
    2
    Rep Power
    0

    Question 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. #2
  3. Transforming Moderator
    Devshed Supreme Being (6500+ posts)

    Join Date
    Mar 2007
    Location
    Washington, USA
    Posts
    14,295
    Rep Power
    9400
    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.
  4. #3
  5. 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...
  6. #4
  7. Transforming Moderator
    Devshed Supreme Being (6500+ posts)

    Join Date
    Mar 2007
    Location
    Washington, USA
    Posts
    14,295
    Rep Power
    9400
    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).

IMN logo majestic logo threadwatch logo seochat tools logo