C# algorithm - find least number of objects necessary

Question

Let's say I have the following code.

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

I want to be able to return 50 & 10 from list to = 60.

If the numberToGetTo was 100 I would want to return 50, 50.

If the numberToGetTo was 85 I would want to return 50, 40.

I want to return the least amount of numbers from the list necessary to get to the "numberToGetTo", while staying closest (equal or greather) than to it.

Is doing something like this with Linq possible?

Answer 1

This is an NP-complete problem called the knapsack problem. That means, that your best method is not going to be in polynomial time. You may have to brute-force a solution.

Answer 2

Here's an implementation that uses Linq to be as clean as possible. It makes no attempt to optimize for performance over large inputs.

I'm assuming that you wouldn't use this algorithm for large inputs anyway, since the problem is NP-Complete, and therefore clarity is the right goal. My algorithm is O(n^2), and recursive at that.

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