最接近/相等的总和(如果有项目列表)-LINQ [英] nearest/equal sum combination if a list of items - LINQ

问题描述

我有一个包含以上属性的项目列表. ID 数量 套餐Nbr 我需要完成的是从该列表中获得金额为 NEAREST OR EQUAL 总和为特定值的项目；但条件应始终有效，即返回的项目应来自不同的PackageNbr. 例如.

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:

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  ║
╚══════╩══════════╩═════════════╝

对于值21，returnedItems的id为:1-6-8

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

对于值14，returnedItems的id为:3-7

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

对于值11，returnedItems的id为:4-9-10

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

我认为可以通过获取所有总和组合(具有不同的PackageNbr)来实现上述目标，然后获得NEAREST或EQUAL.

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.

任何想法如何完成此任务? 我确实在网上冲浪，但找不到使用linq的方法. 任何帮助将不胜感激.

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.

致谢

推荐答案

我认为您的问题映射到计算机科学中众所周知的问题，称为子集总和问题

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:

1. 如果您有一个很少更改的数据集，并且需要使用不同的总和多次查询，只需构建一个包含所有总和的表即可.按总和对它进行排序，并使用二进制搜索来获取具体和的结果.

1. 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.

---

这是选项1的示例实现. 它使用 combinatorics库的NUGet生成组合.

---

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

这篇关于最接近/相等的总和(如果有项目列表)-LINQ的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！