4

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?

Paul
  • 41
  • 3

6 Answers6

13

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.

alt text

Community
  • 1
  • 1
John Gietzen
  • 48,783
  • 32
  • 145
  • 190
  • 5
    I believe the question is posing something much simpler than the knapsack problem. – Drew Dormann Dec 21 '09 at 16:14
  • 1
    Even tho is is a *simplification* of the knapsack problem, it still is the knapsack problem. However, their value system may be to use the fewest possible numbers (as in, larger numbers are rated higher), rather than dollars and cents. – John Gietzen Dec 21 '09 at 16:20
  • 3
    @John: Care to prove that the knapsack problem can be reduced to this? The knapsack problem requires an *exact* size of knapsack to be filled, in this case he is allowed to go over the target number, which means that there always exists a solution, unlike the knapsack problem. This problem may still be NP-complete, but it is not obviously directly the knapsack problem. – tloach Dec 21 '09 at 16:23
  • Actually, for the list {10kg, 20kg, 30kg, 40kg, 50kg}, the values {$1, $2, $4, $8, $16} would make this exactly equivalent to the problem on the Wikipedia main page. – John Gietzen Dec 21 '09 at 16:24
  • 1
    @tloach: crap, I didn't notice that. Then the solution is to always use the largest item as many times as necessary until it overflows the container. – John Gietzen Dec 21 '09 at 16:25
  • AKA, The solution technique for the continuous knapsack: http://en.wikipedia.org/wiki/Continuous_knapsack_problem – John Gietzen Dec 21 '09 at 16:26
6

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();
    }
Jay Bazuzi
  • 45,157
  • 15
  • 111
  • 168
  • +1 for an actual solution, rather than a nod to the Wikipedia article about the knapsack problem. – Erik Forbes Dec 21 '09 at 18:06
  • 1
    the problem is not NP complete. It is proportional to the number of objects in the list and to the difference in size between the largest element of the list and the target number. – Peter Recore Dec 21 '09 at 18:26
  • this throws a sequence has no elements exception? something wrong here? var list = new[] {10, 20, 30, 40, 50}; var res = Knapsack(list, 105); – Paul Dec 21 '09 at 19:16
  • Peter, are you sure? Suppose the goal is 10 and the list is { 2, 6, 9 } - the fact that 9 is in the list doesn't matter. Also, there's a little extra complexity because 2 is used twice. Not sue if it affects your math. – Jay Bazuzi Dec 22 '09 at 05:51
  • @Paul: That's because no combination that adds to the goal. It's not the best exception. Adding `if (!matches.Any()) throw ...` seems good to me, but I'll leave it up to you to decide what suits your purposes best. – Jay Bazuzi Dec 22 '09 at 05:54
  • @Jay - unless there's some clarification on what counts as "best" or "closest", you can always take the largest number that is not higher than the target, use that as many times as it takes to get past the target. In your example, why would you use 2 twice? {9,2} has less numbers than {6,2,2} – Peter Recore Dec 22 '09 at 08:05
  • @Peter: oops, I missed the bit about "or greather" (sic). My algorithm is incorrect in that regard. It's not completely clear form the original question whether a smaller answer set is better than being closer to the goal. – Jay Bazuzi Dec 23 '09 at 07:18
2

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] ?

Peter Recore
  • 14,037
  • 4
  • 42
  • 62
  • 1
    I suppose from the examples he gave, one requirement would be to not use [50, 50] when [50, 10] would suffice, but that's an easy addition - once you've grabbed enough of the highest value to overflow, step down the list until you get the lowest value that will still suffice. – Eclipse Dec 21 '09 at 18:49
  • 1
    Or easier: take floor(target / A), then find the smallest number in the list B s.t. B >= target % A – Eclipse Dec 21 '09 at 18:52
1

Knapsack Problem, this may give you a clue.

http://en.wikipedia.org/wiki/Knapsack_problem

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.

DanC
  • 8,595
  • 9
  • 42
  • 64
0

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

Matthew Groves
  • 25,181
  • 9
  • 71
  • 121
0

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.

Olivieri
  • 370
  • 3
  • 9