最接近期望值的记录的总和

Question

如何编写具有以下结果的方法，如何创建 Filter 方法？最接近期望值的记录的总和

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

}

Answer 1

这是 0/1 Knapsack Problem 的变体，它的解在 space 和时间 O(Tk) 中都是伪多项式的，其中 k 是项目数，T 是预期数。

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

该算法构建了一个可达总数数组。您可以运行反向算法以提取导致您要过滤的特定结果的 ID 序列。

Answer 2

您需要逐步解决这个问题

按值降序排列列表
遍历列表，直到找到等于或小于过滤值的第一个值
创建剩余项目的列表并将它们组合在一起，直到分组项目的总和等于或超过筛选值
最后，检查总和是否超过筛选值，如果是，则删除具有最小值的项目
继续迭代直到列表为空或直到你有一个完全匹配

注意：从某种意义上说，这是一个简单的实现，它将获得紧密匹配而不是完全匹配，如下所示：

values: 3,5,7,9,11

filter value: 19

returns 11, 7 (total : 18)

更好的算法会 return 11, 5, 3 (total: 19) 但这在计算上会更加昂贵，需要对值进行多次迭代。

准确性在您的场景中有多重要？

最接近期望值的记录的总和

The sum of the closest record to the desired value

c#

algorithm

expression

sum