最接近所需值的记录的总和

本文关键字：记录 最接近 | 更新日期: 2023-09-27 18:36:29

如何编写该方法具有以下结果，如何创建过滤器梅托德？最接近所需值的记录的总和

class Program
{
public Program()
{
    List<item> items = new List<item>() 
    {
        new item () { Id = 11 , Value = 100},
        new item () { Id = 12 , Value = 300},
        new item () { Id = 13 , Value = 10},
        new item () { Id = 14 , Value = 20},
        new item () { Id = 15 , Value = 200},
        new item () { Id = 16 , Value = 600},
        new item () { Id = 17 , Value = 7},
        new item () { Id = 18 , Value = 3},
        new item () { Id = 19 , Value = 3},
        new item () { Id = 20 , Value = 2},
        new item () { Id = 21 , Value = 70},
        new item () { Id = 22 , Value = 200},
        new item () { Id = 23 , Value = 300},
        new item () { Id = 24 , Value = 250},
        new item () { Id = 25 , Value = 900},
        new item () { Id = 26 , Value = 700},
        new item () { Id = 27 , Value = 400},
    };
    var list_1 = items.Filter(1000);    //expect id : 11,12,16
    var list_2 = items.Filter(25);      //expect id : 13,17,18,19,20
    var list_3 = items.Filter(400);     //expect id : 11,12
    var list_4 = items.Filter(1935);    //expect id : 11,12,13,14,15,16,18,20,25
    var list_5 = items.Filter(101);     //expect id : 11
    var list_6 = items.Filter(150);     //expect id : 11,13,14,17,18,19,20
}

最接近所需值的记录的总和

这是 0/1 背包问题的变体，该问题在空间（即 O（k））和时间（即 O（Tk））中都是伪多项式的解，其中k是项目数，T是预期数。

上面链接的文章有简单的伪代码来解决问题。应将其修改为使用一对一维数组而不是二维数组以节省内存。这是可能的，因为每次迭代最多引用 2D 数组中的两行 - 正在构造的行和紧靠其前面的行。

该算法构造一个可访问的总计数组。您可以反向运行算法，以提取导致要筛选的特定结果的 ID 序列。

您需要分步解决此问题

  1. 按值降序对列表进行排序
  2. 循环访问列表，直到到达等于或小于筛选器值的第一个值
  3. 创建剩余项目的列表并将它们组合在一起，直到分组项目的总和等于或超过筛选值
  4. 最后，检查总和是否超过过滤器值，如果是，则删除具有最小值的项目
  5. 继续迭代，直到列表为空或完全匹配

注意：这是一个简单的实现，因为它将获得紧密匹配而不是完全匹配，如下所示： 

values: 3,5,7,9,11
filter value: 19
returns 11, 7 (total : 18)

更好的算法将返回11, 5, 3 (total: 19)但这在计算上会更昂贵，需要多次迭代值。

准确性在您的方案中有多重要？

相关文章：