C# - 组合学

Question

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

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

在 C# 中有任何 'clean' 方法可以做到这一点吗？

谢谢！

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

编辑：所有细节都公开后，以下内容应该有所帮助

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

新建一个class

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

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 个对象相比，选择 exaclty maxCount 个对象给你的总分要低。例如，对于商品 [(100, 10), (200,20), (300,30), (500,80)]，maxPrice = 500 和 maxCount = 2 此方法仅 returns (500,80) .如果你想要它 return [(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，它仍然可以 return 其他数量的项目。

C# - 组合学

C# - Combinatorics

c#

asp.net

combinatorics