C# - 组合数学

Question

我有一个包含大约300个对象的列表，每个对象都有一个价格和一个分数。我需要找到其中15个对象的最佳组合（即总分数最高），并且它们的总价格小于X。

据我所知，最直接的方法是嵌套15个for循环并检查每个可能的组合，但这将需要几天时间。

在C#中有没有一种“干净”的方法来实现这个功能？

谢谢！

- T0mba

---

你有考虑过使用linq吗？ - Captain0

由于某种原因，这个问题浮现在脑海中：https://simple.wikipedia.org/wiki/Travelling_salesman_problem - Daniel van Heerden

@T0mba：正如我在上面的评论中所指出的，如果你想在合理的时间内寻找一个最优解决方案，那么你是在做一件愚蠢的事情。已经有超过一个世纪的时间研究了快速次优解决方案；显然，这个问题对于从优化商店货架布局到优先考虑去国际空间站进行实验的任务都非常重要。进行文献搜索，你会发现有很多关于这个主题的论文。 - Eric Lippert

我现在明白了，在阅读有关问题的信息后，我意识到自己之前对问题的复杂性存在误解。 - Captain0

@Captain0 如果你在帖子中提到这是一个在可行的时间内的次优解决方案，我相信它值得一加。 - jsanalytics

Answer 1

没有示例很难提供帮助，但如果我理解了问题，这可能会有所帮助。

假设您的对象看起来像这样

public class Item
{
        public int Score { get; set; }
        public decimal Price { get; set; }
}

那么以下内容应该能帮到你。

var listOfObjects = new List<Item>();

var topItems = listOfObjects.Where(p => p.Price < 100).OrderByDescending(p => p.Score).Take(15);

编辑： 所有细节都已经披露，以下内容应该会有所帮助

免责声明：快速而简单的解决方案（次优）

创建一个新类

public class ItemWithRunningTotal
{
    public Item Item { get; set; }
    public decimal RunningTotal { get; set; }
}

那么以下内容应该能够帮助您获得所需的结果。

var maxTotal = 1500; //for you 8000
        var objects = new List<Item>()
                      {
                          new Item() {Score = 10, Price = 100},
                          new Item() {Score = 20, Price = 800},
                          new Item() {Score = 40, Price = 600},
                          new Item() {Score = 5, Price = 300},
                      };

        decimal runningTotal = 0;
        var newList = objects
            .OrderByDescending(p => p.Score)
            .Select(p =>
                    {
                        runningTotal = runningTotal + p.Price;
                        return new ItemWithRunningTotal()
                               {
                                   Item = p,
                                   RunningTotal = runningTotal
                               };
                    })
            .OrderByDescending(p => p.RunningTotal)
            .Where(p => p.RunningTotal <= maxTotal).Take(15);

- Captain0

---

你的假设是正确的，但恐怕我在问题表达上没有太清楚：这15个物品的总价（总和）不能超过8000，单个物品的价格并不重要。 - T0mba

当总价超过8000时，应该怎么办？应该使用更低价格的商品吗？ - Captain0

是的，确实如此。我们只想在使用15个物品时获得最高可能的分数，而不超过8000的总成本。 - T0mba

Answer 2

你正在寻找背包问题的解决方案。目前还没有已知的快速解决方法。 您可以修改动态规划解决方案（https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem），以选择最多 maxCount 个物品，方法如下：

public static List<Item> BestCombination(List<Item> items, int maxPrice, int maxCount)
{
    var scores = new int[items.Count + 1, maxPrice + 1, maxCount + 1];

    for (int i = 1; i <= items.Count; i++)
    {
        var item = items[i - 1];
        for (int count = 1; count <= Math.Min(maxCount, i); count++)
        { 
            for (int price = 0; price <= maxPrice; price++)
            {                    
                if (item.Price > price)
                    scores[i, price, count] = scores[i - 1, price, count];                
                else
                    scores[i, price, count] = Math.Max(
                        scores[i - 1, price, count],
                        scores[i - 1, price - item.Price, count - 1] + item.Score);
            }
        }
    }

    var choosen = new List<Item>();
    int j = maxPrice;
    int k = maxCount;
    for (int i = items.Count; i > 0; i--)
    {
        var item = items[i - 1];
        if (scores[i, j, k] != scores[i - 1, j, k])
        {
            choosen.Add(item);
            j -= item.Price;
            k--;
        }
    }            

    return choosen;
}

请注意，选择恰好maxCount个对象可能会给您比选择<= maxCount个对象更低的总分数。例如对于项目[(100, 10), (200,20), (300,30), (500,80)], maxPrice = 500且maxCount = 2，此方法仅返回(500,80)。如果您想要返回[(200,20),(300,30)]，您可以像这样初始化数组：

for (int i = 0; i <= items.Count; i++)
{
    for (int price = 0; price <= maxPrice; price++)
    {
        for (int count = 1; count <= maxCount; count++)
        {
            scores[i, price, count] = int.MinValue;
        }
    }
}

确保在scores [,, count]中是count个分数（或MinValue）的总和。但是，如果没有办法精确选择maxCount，它仍然可以返回另一个项目数量。

- jradz