如果项目列表 - LINQ[英] nearest/equal sum combination if a list of items - LINQ

本文是小编为大家收集整理的关于如果项目列表 - LINQ的处理/解决方法,可以参考本文帮助大家快速定位并解决问题,中文翻译不准确的可切换到English标签页查看源文。

问题描述

我有一个包含上述属性的项目列表. ID 数量 Packagenbr 我需要完成的工作是从这个列表中获取具有最接近或相等> 金额总和到特定值的项目;但是条件应始终有效,即返回的项目应来自不同的packagenbr. 例如.

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,返回列的ID为:1-6-8

对于值14,返回列的ID为:3-7

对于值11,返回列的ID为:4-9-10

我认为以上可以通过获得所有总和(具有不同的packagenbr)来实现,然后我们可以获得最近或相等的.

任何想法如何完成这项任务? 我确实在网络上冲浪,没有找到使用LINQ进行操作的方法. 任何帮助将不胜感激.

问候

推荐答案

我认为您的问题映射到计算机科学中众所周知的问题,称为 subset sum问题

如果您没有其他约束,则必须找到所有可能的组合,您最终会使用指数算法.

现在可以实用解决方案:

  1. 如果您有一个很少更改的数据集,并且需要用不同的总和多次查询它,则只需构建一个具有相应总和的所有组合的表即可.通过总和对其进行排序,然后使用二进制搜索获得具体总和的结果.

  2. 如果您的数据集几乎相同,但是相对频繁地更改,您仍然可以使用所有组合和相应的总和创建一个排序的数据结构.但是,然后您需要在每次添加或删除原始数据集中后将其保持最新状态.这仍然比重新再生更便宜.

  3. 如果您始终拥有一个新的数据集和新的查询值,则使用Wiki文章中描述的一种解决方案.


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

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

本文地址:https://www.itbaoku.cn/post/1557046.html

问题描述

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

推荐答案

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

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

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