我整合金矿的算法中的缺陷在哪里? [英] Where is the flaw in my algorithm for consolidating gold mines?

问题描述

设置是给定N对象的列表，例如

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;

我想将黄金整合到K矿山中.

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

我的输出是

3

正确的输出是

4

推荐答案

另一个答案的确指出了实现中的一个缺陷，但是并没有提到在您的代码中您实际上并没有更改Gold值在其余的Mine对象中.因此，即使您确实对数据进行了排序，也无济于事.

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.

此外，在每次迭代中，您真正关心的只是 minimum 值.对整个数据列表进行排序是过大的.您只需扫描一次即可找到最小值的项目.

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.

您实际上也不需要单独的标志数组.只需将移动对象保留在一个列表中，然后在选择移动后，删除包含Mine的移动对象，否则该移动对象将被标记为不再有效.

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);
    }

在您的问题中没有更多细节，我不能保证这确实符合规范.但是它确实会为sum生成值4. :)

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. :)

这篇关于我整合金矿的算法中的缺陷在哪里?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！