nearest/equal sum combination if a list of items - LINQ

Question

I have a list of items that contains the above properties. Id Amount PackageNbr What I need to accomplish, is to get from this list, the items that have the NEAREST OR EQUAL sum of Amount to a specific value; but a condition should always be valid which is that the items returned should be from different PackageNbr. For example.

listOfItems:

╔══════╦══════════╦═════════════╗
║ ID   ║  amount  ║  packageNbr ║
╠══════╬══════════╬═════════════╣
║   1  ║      10  ║          1  ║
║   2  ║       7  ║          1  ║
║   3  ║       4  ║          1  ║
║   4  ║       6  ║          2  ║
║   5  ║       5  ║          2  ║
║   6  ║       3  ║          2  ║
║   7  ║      10  ║          3  ║
║   8  ║       9  ║          3  ║
║   9  ║       3  ║          4  ║
║  10  ║       2  ║          5  ║
╚══════╩══════════╩═════════════╝

for the value 21, id of returnedItems are : 1 - 6 - 8

for the value 14, id of returnedItems are : 3 - 7

for the value 11, id of returnedItems are : 4 - 9 - 10

I think the above can be achieve by getting all the sum combination (that have different PackageNbr), and after that we can get the NEAREST OR EQUAL.

Any idea how to accomplish this task ? I did surf the web and didn't find a way to do it using linq. Any help would be appreciated.

Regards

You have at least 2 combinations to get 21, using 1 - 4 - 9 - 10 You have at least 2 combinations to get 14, using 2 - 5 - 10 or 5 - 8 if you ara going to check all possibilities, you will have a lot work to do. All sum combination possible is something like 4 4 3 2 2 — Alberto Monteiro, Nov 08 '15 at 20:51

George Mamaladze · Accepted Answer · 2015-11-09T23:30:12.110

I think your problem maps to the well known problem in computer science called Subset Sum Problem

To make it short if you do not have additional constraints and have to find all possible combinations you end up with an exponential algorithm.

Now to a practical solution:

If you have one dataset which is rarely changing and you need to query it multiple times with different sums, just build a table of all combinations with corresponding sums. Sort it by sums and use binary search to get results for a concrete sum.
If your dataset is almost the same, but changing relatively frequently, you still can create a sorted data structure with all combinations and corresponding sums once. But then you need to keep it up to date after each add or remove in your original dataset. This will be still cheaper than regenerating it over again.
If you always have a new dataset and new query value you end-up with one of solutions described in wiki article.

This is a sample implementation of option 1. It uses NUGet of combinatorics library to generate combinations.

        //Dataset
        var items = new[] {
            new Item {Id=1, Amount=10, PackageNr=1},
            new Item {Id=2, Amount=7, PackageNr=1},
            new Item {Id=3, Amount=4, PackageNr=2},
            new Item {Id=4, Amount=3, PackageNr=2},
            new Item {Id=5, Amount=8, PackageNr=3},
            new Item {Id=6, Amount=9, PackageNr=3},
            new Item {Id=7, Amount=10, PackageNr=4},
        };


        //Building a table
        var stack = new List<Tuple<int, int[]>>();
        for(int count=1; count <= items.Count(); count++) {
            stack.AddRange(
             new Combinations<Item>(items, count)
                .Where(combination => !combination
                                        .GroupBy(item => item.PackageNr)
                                        .Where(group => group.Count() > 1)
                                        .Any())
                .Select(combination => new Tuple<int, int[]>(
                                        combination.Sum(item=>item.Amount), 
                                        combination.Select(item=>item.Id).ToArray())));
        }

        var table = 
            stack
            .OrderBy(tuple => tuple.Item1)
            .ToArray();
        var index = table.Select(i => i.Item1).ToArray(); 

        //Print the table
        foreach (var row in table)
        {
            Console.WriteLine(" {0} ->  {1}", row.Item1, string.Join(",", row.Item2));
        };


        //Binary search in the table.
        Console.WriteLine("Number to search for:");
        int number;
        int.TryParse(Console.ReadLine(), out number);

        var position = Array.BinarySearch(index, number);
        if (position >= 0) Console.WriteLine("Exact match {0}", string.Join(",", table[position].Item2));
        else Console.WriteLine("Best match {0}", string.Join(",", table[~position].Item2));
        Console.ReadKey();
    }

I have only one dataset which is rarely changing. So is there a way to achieve the solution number 1 from linQ ? — Nabz, Nov 09 '15 at 16:41
the BinarySearch isn't working well. sometimes it reply with a negative position, and the table[~position].Item2 returns a System.IndexOutOfRangeException.(You can try the number 50,41,123,....) — Nabz, Dec 21 '15 at 09:24
@Nabz I forgot to mention that return value of binary seach is not always index. In case of the negative number returned it is the bitwise complement of the index of the first element that is larger than value. To get best match index you have to apply `~` operator. `var index = index<0 ? ~index : index;`. See https://gmamaladze.wordpress.com/2011/07/22/back-to-the-roots-net-binary-search-and-the-meaning-of-the-negative-number-of-the-array-binarysearch-return-value/ — George Mamaladze, Dec 21 '15 at 10:04

nearest/equal sum combination if a list of items - LINQ

1 Answers1