Where is the flaw in my algorithm for consolidatin

问题:

The setup is that, given a list of N objects like

class Mine
{
    public int Distance { get; set; } // from river
    public int Gold { get; set; } // in tons
}

where the cost of moving the gold from one mine to the other is

    // helper function for cost of a move
    Func<Tuple<Mine,Mine>, int> MoveCost = (tuple) => 
        Math.Abs(tuple.Item1.Distance - tuple.Item2.Distance) * tuple.Item1.Gold;

I want to consolidate the gold into K mines.

I've written an algorithm, thought it over many times, and don't understand why it isn't working. Hopefully my comments help out. Any idea where I'm going wrong?

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Mine
{
    public int Distance { get; set; } // from river
    public int Gold { get; set; } // in tons
}

class Solution 
{
    static void Main(String[] args) 
    {
        // helper function for reading lines
        Func<string, int[]> LineToIntArray = (line) => Array.ConvertAll(line.Split(' '), Int32.Parse);

        int[] line1 = LineToIntArray(Console.ReadLine());
        int N = line1[0], // # of mines
            K = line1[1]; // # of pickup locations

        // Populate mine info
        List<Mine> mines = new List<Mine>();
        for(int i = 0; i < N; ++i)
        {
            int[] line = LineToIntArray(Console.ReadLine());
            mines.Add(new Mine() { Distance = line[0], Gold = line[1] });
        }

        // helper function for cost of a move
        Func<Tuple<Mine,Mine>, int> MoveCost = (tuple) => 
            Math.Abs(tuple.Item1.Distance - tuple.Item2.Distance) * tuple.Item1.Gold;

        // all move combinations
        var moves = from m1 in mines
                    from m2 in mines
                    where !m1.Equals(m2)
                    select Tuple.Create(m1,m2);

        // moves in ascending order of cost
        var ordered = from m in moves
                      orderby MoveCost(m)
                      select m;

        int sum = 0; // running total of move costs
        var spots = Enumerable.Repeat(1, N).ToArray(); // spots[i] = 1 if hasn't been consildated into other mine, 0 otherwise
        var iter = ordered.GetEnumerator();
        while(iter.MoveNext() && spots.Sum() != K)
        {
            var move = iter.Current; // move with next smallest cost
            int i = mines.IndexOf(move.Item1), // index of source mine in move
                j = mines.IndexOf(move.Item2); // index of destination mine in move
            if((spots[i] & spots[j]) == 1) // if the source and destination mines are both unconsolidated
            {
                sum += MoveCost(move); // add this consolidation to the total cost
                spots[i] = 0; // "remove" mine i from the list of unconsolidated mines 
            }
        }

        Console.WriteLine(sum);
    }
}

An example of a test case I'm failing is

3 1
11 3
12 2
13 1

My output is

3

and the correct output is

4

回答1:

The other answer does point out a flaw in the implementation, but it fails to mention that in your code, you aren't actually changing the Gold values in the remaining Mine objects. So even if you did re-sort the data, it wouldn't help.

Furthermore, at each iteration all you really care about is the minimum value. Sorting the entire list of data is overkill. You can just scan it once to find the minimum-valued item.

You also don't really need the separate array of flags. Just maintain your move objects in a list, and after choosing a move, remove the move objects that include the Mine you would otherwise have flagged as no longer valid.

Here is a version of your algorithm that incorporates the above feedback:

    static void Main(String[] args)
    {
        string input =
@"3 1
11 3
12 2
13 1";
        StringReader reader = new StringReader(input);

        // helper function for reading lines
        Func<string, int[]> LineToIntArray = (line) => Array.ConvertAll(line.Split(' '), Int32.Parse);

        int[] line1 = LineToIntArray(reader.ReadLine());
        int N = line1[0], // # of mines
            K = line1[1]; // # of pickup locations

        // Populate mine info
        List<Mine> mines = new List<Mine>();
        for (int i = 0; i < N; ++i)
        {
            int[] line = LineToIntArray(reader.ReadLine());
            mines.Add(new Mine() { Distance = line[0], Gold = line[1] });
        }

        // helper function for cost of a move
        Func<Tuple<Mine, Mine>, int> MoveCost = (tuple) =>
            Math.Abs(tuple.Item1.Distance - tuple.Item2.Distance) * tuple.Item1.Gold;

        // all move combinations
        var moves = (from m1 in mines
                    from m2 in mines
                    where !m1.Equals(m2)
                    select Tuple.Create(m1, m2)).ToList();

        int sum = 0, // running total of move costs
            unconsolidatedCount = N;
        while (moves.Count > 0 && unconsolidatedCount != K)
        {
            var move = moves.Aggregate((a, m) => MoveCost(a) < MoveCost(m) ? a : m);

            sum += MoveCost(move); // add this consolidation to the total cost
            move.Item2.Gold += move.Item1.Gold;
            moves.RemoveAll(m => m.Item1 == move.Item1 || m.Item2 == move.Item1);
            unconsolidatedCount--;    
        }

        Console.WriteLine("Moves: " + sum);
    }

Without more detail in your question, I can't guarantee that this actually meets the specification. But it does produce the value 4 for the sum. :)

回答2:

When you consolidate mine i into mine j, the amount of gold in the mine j is increased. This makes consolidations from mine j to other mines more expensive potentially making the ordering of the mines by the move cost invalid. To fix this, you could re-sort the list of mines at the beginning of each iteration of your while-loop.