c# - 最接近期望值的记录的总和

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 的变体，它有一个在空间 O(k) 和时间 O(Tk) 上都是伪多项式的解，其中 k 是项目数， T 是预期的数字。

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

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