时间戳

首页 > 解决方案 > 如何解决高级编码竞赛中提出的这个问题？

algorithm - 如何解决高级编码竞赛中提出的这个问题？

问题描述

有人可以指导我如何解决这个编程问题吗？这似乎是我找不到答案的 DP 问题。

问题：

有“n”个广告。每个广告都有一个与之关联的有效性值，该值以 [v1, v2, ..., vn] 格式在大小为“n”的数组中给出，其中“v1”是第一个广告的有效性值，“v2”是第二个广告的效果值，以此类推。展示这些广告的节目长度为 'm' 长（从 0 到 m），并且可以展示广告的时间以 [(a1, b1), (a2, b2), ..., (an, bn)]，其中数组中的第 i 个元组表示格式为 (start_time, end_time) 的第 i 个广告的时间。请注意，任何“ai”和“bi”都不能小于 0，也不能大于“m”。当您选择展示广告时，您不能在广告结束后的 4 分钟内展示另一个广告。因此，如果您选择展示时间为 (2, 4) 的广告，那么您不能在 9 之前展示另一个广告，因此下一个广告不能是 (8, 10)，但可以是 (9, 12)。在给定上述限制的情况下，您必须选择要向受众展示的广告，以便最大化广告的有效性值的总和。例如，如果 'm' 为 20，则广告的时间为 [(2, 3), (6, 9), (10, 12), (12, 13), (14, 17)] 并且有效性值为 [3, 9, 10, 6, 7]，然后您可以显示广告 2 和广告 5（基于 1 的索引）并且有效性值为 16，这是在给定约束条件下可以获得的最大值。

标签： algorithmdynamic-programmingknapsack-problemgreedy

解决方案

您的问题可以简化为以下问题，让我们考虑可以描述为 (start_i, end_i, value_i) 的 1d 段。

让 S = 可用一维段的数组

我们想要的是找到总和为最大可能值并适合区间 [0, m] 的非相交段（显示长度）

令 DP[x] = 用可用 1d 段的子集覆盖段 [0, x] 的最佳可实现值。

递归关系是，给定一个元素（s_i，e_i，v_i），我们可以选择或不选择它。

DP[e_i] = DP[e_i - 1]

DP[e_i] = 最大值（DP[e_i]，DP[s_i - 1] + v_i）

dp[0] = 0;
// sort the events by increasing e_i, because
// we want to process first the events that finish earlier

for( int END = 1; END <= m; ++END)
{
    dp[end] = dp[end - 1];
    for( each ELEMENT(s_i, e_i, v_u) with (e_i == END) )
    {
        dp[end] = max( dp[end], dp[s_i - 1] + v_i ) 
    }
}

推荐阅读