algorithm - 火车行程分组算法

Question

想象你面前有一个完整的日历年。有时你会坐火车，甚至可能一天几次，每次旅行可能会到不同的地方（即每次旅行你支付的车票金额可能不同）。
所以你会得到这样的数据：

Date: 2018-01-01, Amount: $5
Date: 2018-01-01, Amount: $6
Date: 2018-01-04, Amount: $2
Date: 2018-01-06, Amount: $4
...

现在您必须将这些数据分组到bucket中。一个bucket最多可以连续31天（没有间隔），并且不能与另一个bucket重叠。
如果一个桶的火车行程少于32次，它将是蓝色的。如果里面有32趟或更多的火车，它会是红色的。bucket还将根据票务成本的总和得到一个值。
你把所有的旅行都分组后，蓝色的水桶就会被扔掉。所有红桶的价值加起来，我们称之为奖品。
目的，是为了获得最高的奖金。
这就是我的问题我想不出一个好的算法来做这件事。如果有人知道解决这个问题的好方法，我想听听或者如果你知道其他地方可以帮助设计这样的算法。

Answer 1

这可以通过动态规划来解决。
首先，按日期对记录进行排序，并按顺序进行考虑。
让day (1)，day (2)，…，day (n)成为买票的日子。
设cost (1)，cost (2)，…，cost (n)为各自的票价。
如果我们只考虑第一个记录，就让fun (k)成为最佳奖。
我们的动态编程解决方案将计算k，fun (0)，fun (1)，…，fun (2)，fun (n-1)，使用前面的值计算下一个值。
基础：
fun (n)。
过渡：
如果我们只考虑前几条记录，那么最佳解决方案是什么？
有两种可能：fun (0) = 0-th记录被丢弃，然后解决方案与fun (k)相同，或者k-th记录是存储桶的最后一条记录。
然后让我们考虑一个循环中以k-th记录结尾的所有可能的bucket，如下所述。
查看记录fun (k-1)，k，k，…，直到第一条记录。
设当前索引为k。
如果从k-1到k-2的记录连续超过i天，则断开循环。
否则，如果记录数i至少k，我们可以解决子问题31，然后将k-i+1中的记录添加到32，获得fun (i-1)的奖励。
值i是这些可能性的最大值，同时也有可能删除k第记录。
答：这只是我们考虑所有记录的情况。
在伪代码中：

fun[0] = 0
for k = 1, 2, ..., n:
    fun[k] = fun[k-1]
    cost_i_to_k = 0
    for i = k, k-1, ..., 1:
        if day[k] - day[i] > 31:
            break
        cost_i_to_k += cost[i]
        if k-i+1 >= 32:
            fun[k] = max (fun[k], fun[i-1] + cost_i_to_k)
return fun[n]

目前尚不清楚是否允许我们将一天的记录拆分成不同的存储桶。
如果答案是否定的，我们将不得不强制执行它，不考虑桶在一天内的记录之间开始或结束。
从技术上讲，它可以通过几个 cost (i) + cost (i+1) + ... + cost (k)语句来完成。
另一种方法是考虑天数而不是记录：我们将使用天数来代替具有 fun (k)和 k的票。
每天将有 fun (n)，当天的总票价，以及 if，票数。
编辑：根据评论，我们确实不能分割任何一天。
然后，经过一些预处理以获取天记录而不是票记录，我们可以用伪代码执行以下操作：

fun[0] = 0
for k = 1, 2, ..., n:
    fun[k] = fun[k-1]
    cost_i_to_k = 0
    quantity_i_to_k = 0
    for i = k, k-1, ..., 1:
        if k-i+1 > 31:
            break
        cost_i_to_k += cost[i]
        quantity_i_to_k += quantity[i]
        if quantity_i_to_k >= 32:
            fun[k] = max (fun[k], fun[i-1] + cost_i_to_k)
return fun[n]

这里， day和 cost是天数。
注意，我们考虑范围内的所有可能日期：如果某一天没有票，我们只使用零作为其 cost和 quantity值。
编辑2：
上面允许我们计算最大总奖金，但是桶的实际配置如何让我们到达那里？
一般的方法是回溯法：在 i位置，我们想知道我们是如何得到 k的，如果最佳的方法是跳过第条记录，则转换到 cost，或者对于方程 quantity所支持的这样的 k从 fun (k)转换到 k-1。
我们继续直到 k降到零。
两种常用的实现方法之一是存储 k，一个“父”，以及 i-1，它编码了我们得到最大值的方式。
假设，如果 i，则最优解跳过第条记录。
否则，我们将最优索引 fun[k] = fun[i-1] + cost_i_to_k存储在 i中，这样最优解需要一桶记录 par (k)到 fun (k)包含。
另一种方法是不存储任何额外的内容。
相反，我们运行一个小的修改代码来计算 par (k) = -1。
但是，我们没有把事情分配给 k，而是将分配的正确部分与我们已经得到的最终值进行比较。
他们一平等，我们就找到了正确的过渡。
在伪代码中，使用第二种方法，使用天而不是单个记录：

k = n
while k > 0:
    k = prev (k)

function prev (k):
    if fun[k] == fun[k-1]:
         return k-1
    cost_i_to_k = 0
    quantity_i_to_k = 0
    for i = k, k-1, ..., 1:
        if k-i+1 > 31:
            break
        cost_i_to_k += cost[i]
        quantity_i_to_k += quantity[i]
        if quantity_i_to_k >= 32:
            if fun[k] == fun[i-1] + cost_i_to_k:
                writeln ("bucket from $ to $: cost $, quantity $",
                    i, k, cost_i_to_k, quantity_i_to_k)
                return i-1
    assert (false, "can't happen")