如何将项目{a_0，.，a_N}合并为K个组，以便合并过程成本最低

让我举一个例子来说明我的意思。假设我有N=3项{ A, B, C }，并希望将它们合并到K组（0 < K < N）中。例如，将它们合并到K=2组中可能会产生结果

{ {A, B}, {C} }

我有一个函数Cost(X, Y) >= 0，它返回将项目X合并为项目Y的成本。例如，如果Cost(A, B) = 10和Cost(B, C) = 15产生

{ {A, B}, {C} }

成本10和生产

{ {A}, {B, C} }

成本为CCD_ 12。

代价函数不是可交换的（Cost(X, Y) = Cost(Y, X)并不总是成立的）。

我想做的是找到一种将成本最低的合并到K组中的算法。

例如，假设成本是

Cost(A, B) = 12
Cost(B, A) = 4
Cost(A, C) = 5
Cost(C, A) = 11
Cost(B, C) = 3
Cost(C, B) = 20

我想合并成CCD_ 15组。成本最低的是

B -> C
A -> C

代价为CCD_ 16。

我正试图找出一个如何确定这一点的概括方法。

我认为它应该如何开始是订购所有成本：

Cost(B, C) = 3
Cost(B, A) = 4
Cost(A, C) = 5
Cost(C, A) = 11
Cost(A, B) = 12
Cost(C, B) = 20

以上列表中的项目将始终是合并过程中的一个移动：

B -> C

现在，我怀疑需要进行的是遍历列表的其余部分，看看是否每次合并。

列表中的下一项是B -> A。由于我已经将B移到了C，所以跳过这个。

下一项是A -> C。由于A尚未合并为一个组，因此这是一个有效的合并。

现在我们已经完成了，因为我们有了K=1组，{ {A, B, C} }。

我想知道如何编写这个算法。

更具体地说，这里有一个C#设置：

using System;
using System.Collections.Generic;
using System.Linq;
public class Widget
{
    public int Distance { get; set; }
    public int Weight { get; set; } 
    public static int Cost(Widget w1, Widget w2)
    {
        // returns the cost of consolidating w1 into w2
        return Math.Abs(w1.Distance - w2.Distance) * w1.Weight; 
    }
}
public class Program
{
    public static void Main()
    {
        var widgets = new List<Widget>() 
        {
            new Widget() { Distance = 10, Weight = 1 },
            new Widget() { Distance = 20, Weight = 1 },
            new Widget() { Distance = 30, Weight = 1 },
        };
        var tuples = from x in widgets
                     from y in widgets
                     where !x.Equals(y)
                     select Tuple.Create(x,y);
        var ordered = from t in tuples
                      orderby Widget.Cost(t.Item1, t.Item2)
                      select t;
        int K = 2;
        int sum = 0; 
        // ... What to do here??? 
        Console.WriteLine(sum); // should write 10
    }
}

仅供参考，这不是家庭作业问题或其他问题。我这么做是为了好玩。