选择数据的算法，使它们的总和是指定的数字，但更喜欢旧数据

Question

我正在尝试实现具有以下要求的功能，但很难想出一个算法。

我的数据包含一个正整数值和一个日期。数据数量从100 ~ 10,000不等。

-------------------------
 id | value |    date
-------------------------
 1  | 10    | 2015-01-01
 2  | 10    | 2015-01-02
 3  | 20    | 2015-01-02
  ....................
960 | 30    | 2015-09-10
961 | 15    | 2015-09-10

还有一个指定的目标值，比如 5,000。

我想找到数据的组合，使它们的值之和等于目标值，并且它们包含尽可能多的旧数据。 (目标数必须匹配，不用先用最早的数据有组合也可以)

谁能告诉我如何实现它？

Answer 1

一种基于子集求和伪多项式解的方法可能是:

首先，对条目进行排序，使最旧的条目排在最后，最新的条目排在最前面。然后，根据以下公式生成 DP 矩阵:

D(i,0) = true
D(0,x) = false         x!= 0
D(i,x) = D(i-1,x) OR D(i-1, x-value[i])

这个矩阵的大小是(n+1) * (target+1)。

接下来，如果可能的话，通过贪婪地选择(从最后到第一个)获取元素来生成一个解决方案:

t = target
i = n
sol = [] //empty list
while (t != 0):
    if D(i-1,t-value[i] == true):
        sol.append(i) //item i in the solution
        t = t - value[i]
    i = i-1 //either case

这保证:

1. sol 的值与目标之和
2. 任何可行解中最旧的值将在 sol 中。