我们有一系列项目 1, ... , n 并且每个项目都有一个分数 (i)。如果我们选择一个项目，那么我们不能选择第 i+1, ... i+rest(i) 个项目。目标是使总分最大化。
我们可以用动态规划来解决这个问题。
对于第一项，我们有两个选择。或选择它并转到其余(1) + 1 项或不选择它并转到第二项。
递归函数:
c[i] = max{ c[i - 1], c[i + rest(i) + 1] + score(i) }
这个递归函数的问题是它在子问题之间创建循环，这意味着子问题不是独立的。
我觉得最好有类似的东西
c[i] = max{ c[i - 1], c[i - itemThatWentToItem(i)] + score(i) }
也许一个解决方案是拥有一个函数，该函数给出导致项目 i 的所有项目，然后取它们之间的最大分数。
另一个想法是将此问题转化为 DAG 中的最长路径问题，并对所有子图进行此操作。
有什么想法吗？
最佳答案
补充评论。是的，它可以用递归来实现，比如:
def C(i, n):
if i > n:
return 0
return max(C(i+1, n), C(i+rest(i)+1)+score(i))
print C(0,n)
从后面计算值是最好的(最快的)。喜欢(注意:数组索引为 1 到 n):
# initialize array with lot of zeros: length + max score(i)
cs = [0] * (n+max(rest(i) for i in range(0,n)+1)
for i in range(n, 0, -1):
cs[i] = max(cs[i+1], cs[i+rest(i)+1]+score(i))
print cs[1]
关于algorithm - 以最大增益顺序跳跃 - 动态规划，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40806358/