C# - 组合学

Question

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

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

在 C# 中是否有任何“干净”的方法来执行此操作？

谢谢!

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