C#算法 - 找到所需的最少对象数

Question

假设我有以下代码.

var numberToGetTo = 60; 
var list = new[] {10, 20, 30, 40, 50};

我希望能够从列表返回50和10到= 60.

如果numberToGetTo为100,我想要返回50,50.

如果numberToGetTo是85,我想要返回50,40.

我想从列表中返回最少量的数字来获得"numberToGetTo",同时保持最接近(相等或更大)而不是它.

可以用Linq做这样的事吗？

Answer 1

这是一个NP完全问题,称为背包问题.这意味着,你最好的方法不会是多项式时间.您可能需要暴力破解解决方案.

Answer 2

这是一个使用Linq尽可能干净的实现.它没有尝试优化大输入的性能.

我假设你不会将此算法用于大输入,因为问题是NP-Complete,因此清晰度是正确的目标.我的算法是O(n ^ 2),并且递归.

    static IEnumerable<int> Knapsack(IEnumerable<int> items, int goal)
    {
        var matches = from i in items
                      where i <= goal
                      let ia = new[] {i}
                      select i == goal ? ia : Knapsack(items, goal - i).Concat(ia);

        return matches.OrderBy(x => x.Count()).First();
    }