与最大增益 - 动态编程顺序跳跃

Question

我们有一系列项目1，...，n，每个项目都有一个分数（i）。如果我们选择一个项目，那么我们将无法选择i 1，... i 休息（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中最长的路径，并为所有子图进行操作。

有什么想法？

Answer 1

在评论中增加。是的，它可以通过递归来实现，例如：

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]