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

Knapsack Problem, this may give you a clue.

http://en.wikipedia.org/wiki/Knapsack%5Fproblem

I'd say that you could create a lambda expression containing the actual alogrithm, but you'll need to use C#. Using 'just linq' will not be enough.

Answer 3

This sounds similar to the Subset sum problem, which can be solved in a reasonable amount of time for smallish sets using dynamic programming. It's not an easy or common problem, so you won't find a helpful Linq extension method for it :)

Answer 4

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

Answer 5

This problem as currently stated is actually trivial. The easiest way to to get "equal or greater" than the target is to find the largest number A in the list, and stick it in the answer list N times, where N is the lowest N such that N * A > target.

I suspect this is not what the original poster really wants however. If the problem is restated to somehow measure the "closeness" of various answers, and make a distinction as to whether answers that are "closer" or answers that have less numbers are "better" then it becomes tougher. For example, if the target is 100, is an answer of [55,55] better or worse than an answer of [20,20,20,20,20] ?

Answer 6

I just hacked this together and I'm sure someone could improve. But does something like this work?

public class App
{
    static void Main(string[] eventArgs)
    {
        var list = new[] {10, 20, 30, 40, 50};
        var whatYouNeed = GetWhatYouNeed(list, 60, 60);
        //what you need will contain 50 & 10

       //whatYouNeed = GetWhatYouNeed(list, 105,105);
        //what you need will contain (50,50, 10)
    }

    private static IList<int> _whatYouNeed = new List<int>();


    static IEnumerable<int> GetWhatYouNeed(IEnumerable<int> list, int goal, int amountRequired)
    {   //this will make sure 20 is taken over 10, if the goal is 15. highest wins
        var intYouNeed = list.OrderBy(x => Math.Abs(amountRequired - x)).FirstOrDefault(x => x > amountRequired);
        if (intYouNeed == 0) intYouNeed = list.OrderBy(x => Math.Abs(amountRequired - x)).FirstOrDefault();
        _whatYouNeed.Add(intYouNeed);

        if (_whatYouNeed.Sum() < goal)
        {
            int howMuchMoreDoYouNeed = goal - _whatYouNeed.Sum();
            GetWhatYouNeed(list, goal, howMuchMoreDoYouNeed);
        }

        return _whatYouNeed;
    }
}

I was a bit lazy passing in two values to GetWhatYouNeed but you get the point.