算法 - 加权区间调度问题变体
Algorithm - Weighted interval scheduling problem variant
所以我遇到了如下问题：
Xzqthpl is an alien living on the inconspicuous Kepler-1229b planet, a
mere 870 or so light years away from Earth. Whether to see C-beams
outside Tannhäuser Gate or just visiting Sirius for a good suntan,
Xzqthpl enjoys going on weekend trips to different faraway stars and
galaxies. However, because the universe is expanding, some of those
faraway places are going to move further and further away from
Kepler-1129b as time progresses. As a result, at some point in the
distant future even relatively nearby galaxies like Andromeda will be
too far away from Kepler-1229b for Xzqthpl to be able to do a weekend
trip there because the journey back and forth would take too much
time. There is a list of "n" places of interest to potentially visit.
For each place, Xzqthpl has assigned a value "v_i" measuring how
interested Xzqthpl is in the place, and a value "t_i" indicating the
number of weeks from now after which the place will be too far away to
visit.
Now Xzqthpl would like to plan its weekend trips in the following way:
- No place is visited more than once.
- At most one place is visited each week.
- Place "i" is not visited after week "t_i"
- The sum of values "v_i" for the visited places is maximized
Design an efficient (polynomial in "n" and independent of the v_i’s
and t_i’s assuming the unit cost model) algorithm to solve Xzqthpl’s
travel planning problem.
目前我真的不知道从哪里开始。这感觉像是 "Weighted Interval Scheduling" 算法的一个奇怪变体（尽管我不确定）。有人可以给我一些关于从哪里开始的提示吗？
我最初的想法是按 "t_i" 升序对列表进行排序...但我不确定在那之后该怎么做（我的想法甚至可能是错误的）。
谢谢！
您可以为此使用最小堆：
算法
- 按ti
对输入进行排序
- 创建一个空的最小堆，它将包含保留的 vi
- 迭代排序的输入。对于每个 i：
- 如果 ti < 堆的大小，那么这意味着不能保留该元素，除非另一个先前选择的元素被踢出出去。检查堆中的最小值是否小于vi。如果是这样，那么最好从堆中取出最小值，并将此 vi 代替。
- 否则，只需将vi添加到堆中即可。
- 在任何一种情况下，保持堆的总值更新
- Return堆总值
为什么这有效
这行得通，因为在每次迭代中我们都有这个不变量：
堆的大小同时表示两个事物。两者都是：
- 我们仍然认为可能成为最终解决方案的候选项的数量，以及
- 已经过去的周数。
想法是堆中的每个项目都分配给一个星期，因此我们需要的周数与堆中的项目数一样多。
因此，在每次迭代中，我们都尝试在 1 周内取得进展。但是，如果下一个访问的项目只能在已经过去的时间段内被允许（即它的最后可能的一周是已经 passed 的一周），那么我们不能只添加它喜欢堆，因为没有可用的一周。相反，我们检查所考虑的项目是否会更好地与我们已经选择的项目交换（并且在堆中）。如果我们交换它，输掉的那一个不能留在堆里，因为现在我们没有可用的一周 that 一个（记住它的时间限制更严格 - - 我们按时间限制的顺序访问它们）。因此，无论我们交换与否，堆大小都保持不变。
其次，堆必须是堆，因为我们想要一种有效的方法总是知道哪个是最少[=75=的元素] 价值。否则，如果它是一个简单的列表，我们将不得不在每次迭代中扫描该列表，以便将其值与我们当前正在处理的列表进行比较（并且可能希望交换）。显然，只有当堆的总价值增加时，交换才会有利可图。所以我们需要一种有效的方法来快速找到 bad 值。最小堆提供了这一点。
一个实现
这是 Python 中的一个实现：
from collections import namedtuple
from heapq import heappush, heapreplace
Node = namedtuple("Node", "time,value")
def kepler(times, values):
n = len(values)
# Combine corresponding times and values
nodes = [Node(times[i], values[i]) for i in range(n)];
nodes.sort() # by time
totalValue = 0
minheap = []
for node in nodes:
if node.time < len(minheap): # Cannot be visited in time
leastValue = minheap[0] # See if we should replace
if leastValue < node.value:
heapreplace(minheap, node.value) # pop and insert
totalValue += node.value - leastValue
else:
totalValue += node.value
heappush(minheap, node.value)
return totalValue
这是它的一些示例输入：
times = [3,3,0,2,6,2,2]
values =[7,6,3,2,1,4,5]
value = kepler(times, values)
print(value) # 23
时间复杂度
排序将代表 O(nlogn) 时间复杂度。即使可以考虑一些基数排序将其降低到 O(n)，堆的使用也代表了 O(nlogn)[= 的最坏情况75=]。所以该算法的时间复杂度为O(nlogn).
所以我遇到了如下问题：
Xzqthpl is an alien living on the inconspicuous Kepler-1229b planet, a mere 870 or so light years away from Earth. Whether to see C-beams outside Tannhäuser Gate or just visiting Sirius for a good suntan, Xzqthpl enjoys going on weekend trips to different faraway stars and galaxies. However, because the universe is expanding, some of those faraway places are going to move further and further away from Kepler-1129b as time progresses. As a result, at some point in the distant future even relatively nearby galaxies like Andromeda will be too far away from Kepler-1229b for Xzqthpl to be able to do a weekend trip there because the journey back and forth would take too much time. There is a list of "n" places of interest to potentially visit. For each place, Xzqthpl has assigned a value "v_i" measuring how interested Xzqthpl is in the place, and a value "t_i" indicating the number of weeks from now after which the place will be too far away to visit.
Now Xzqthpl would like to plan its weekend trips in the following way:
- No place is visited more than once.
- At most one place is visited each week.
- Place "i" is not visited after week "t_i"
- The sum of values "v_i" for the visited places is maximized
Design an efficient (polynomial in "n" and independent of the v_i’s and t_i’s assuming the unit cost model) algorithm to solve Xzqthpl’s travel planning problem.
目前我真的不知道从哪里开始。这感觉像是 "Weighted Interval Scheduling" 算法的一个奇怪变体（尽管我不确定）。有人可以给我一些关于从哪里开始的提示吗？
我最初的想法是按 "t_i" 升序对列表进行排序...但我不确定在那之后该怎么做（我的想法甚至可能是错误的）。
谢谢！
您可以为此使用最小堆：
算法
- 按ti 对输入进行排序
- 创建一个空的最小堆，它将包含保留的 vi
- 迭代排序的输入。对于每个 i：
- 如果 ti < 堆的大小，那么这意味着不能保留该元素，除非另一个先前选择的元素被踢出出去。检查堆中的最小值是否小于vi。如果是这样，那么最好从堆中取出最小值，并将此 vi 代替。
- 否则，只需将vi添加到堆中即可。
- 在任何一种情况下，保持堆的总值更新
- Return堆总值
为什么这有效
这行得通，因为在每次迭代中我们都有这个不变量：
堆的大小同时表示两个事物。两者都是：
- 我们仍然认为可能成为最终解决方案的候选项的数量，以及
- 已经过去的周数。
想法是堆中的每个项目都分配给一个星期，因此我们需要的周数与堆中的项目数一样多。
因此，在每次迭代中，我们都尝试在 1 周内取得进展。但是，如果下一个访问的项目只能在已经过去的时间段内被允许（即它的最后可能的一周是已经 passed 的一周），那么我们不能只添加它喜欢堆，因为没有可用的一周。相反，我们检查所考虑的项目是否会更好地与我们已经选择的项目交换（并且在堆中）。如果我们交换它，输掉的那一个不能留在堆里，因为现在我们没有可用的一周 that 一个（记住它的时间限制更严格 - - 我们按时间限制的顺序访问它们）。因此，无论我们交换与否，堆大小都保持不变。
其次，堆必须是堆，因为我们想要一种有效的方法总是知道哪个是最少[=75=的元素] 价值。否则，如果它是一个简单的列表，我们将不得不在每次迭代中扫描该列表，以便将其值与我们当前正在处理的列表进行比较（并且可能希望交换）。显然，只有当堆的总价值增加时，交换才会有利可图。所以我们需要一种有效的方法来快速找到 bad 值。最小堆提供了这一点。
一个实现
这是 Python 中的一个实现：
from collections import namedtuple
from heapq import heappush, heapreplace
Node = namedtuple("Node", "time,value")
def kepler(times, values):
n = len(values)
# Combine corresponding times and values
nodes = [Node(times[i], values[i]) for i in range(n)];
nodes.sort() # by time
totalValue = 0
minheap = []
for node in nodes:
if node.time < len(minheap): # Cannot be visited in time
leastValue = minheap[0] # See if we should replace
if leastValue < node.value:
heapreplace(minheap, node.value) # pop and insert
totalValue += node.value - leastValue
else:
totalValue += node.value
heappush(minheap, node.value)
return totalValue
这是它的一些示例输入：
times = [3,3,0,2,6,2,2]
values =[7,6,3,2,1,4,5]
value = kepler(times, values)
print(value) # 23
时间复杂度
排序将代表 O(nlogn) 时间复杂度。即使可以考虑一些基数排序将其降低到 O(n)，堆的使用也代表了 O(nlogn)[= 的最坏情况75=]。所以该算法的时间复杂度为O(nlogn).