以最大增益顺序跳转 - 动态编程

我们有一系列项目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) }

也许一个解决办法是有一个功能，让所有导致项目我，然后把它们之间的最大比分的项目。

另一个想法是将此问题转换为DAG中的最长路径，并针对所有子图执行此操作。

任何想法？

来源

2016-11-25 Laxmana

从端计算它：C [1] = MAX {C [1 + 1]，C [1 +其余（ⅰ）+ 1] +评分（i）} – Ante

愚蠢的问题，但我可以在递归函数中做到这一点？最后的解决方案是c [0]？ – Laxmana

除了注释。是的，它可以用递归来实现，这样的：

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]

来源

2016-11-25 20:37:34 Ante

谢谢！知道我理解得更好。我认为从理论/数学的角度来看，你无法从最终计算出来。没有理由为什么:)。 – Laxmana

一般来说，在递归函数中，我可以去c [i - 1]或c [i + 1]（取决于问题），对吧？ – Laxmana

想法是通过解决更简单的类似子问题来解决问题。在这种情况下，最简单的子问题是最后一个元素，因为它不影响其他任何元素，只有一个组合。然后，最后两个元素，有两个组合...因此，从后面解决它更容易。 – Ante

以最大增益顺序跳转 - 动态编程

回答

相关问题