動態規劃方法

Question

我在想，如果你可能有一些洞察到一個問題，我們考慮的優化問題：

最大Σ從j = 1到FJ（XJ）正使得Σj = 1至XJ正< = B

XJ> = 0，整數

其中B是正整數和fj是真實實際

我試圖使用動態編程配製的溶液，並找出這種方法的時間複雜度。

林有點困惑的動態規劃方法，你將如何實現它的功能，例如F1（X）=開方如果n = 5，B = 10

親切的問候

Answer 1

（X）

您的問題是解決

max(g(n,s) for s=0 to B) 

其中s是sum(x[i] for i = 1 to j)

其中g可以遞歸表示爲

g(0,s) = 0 
g(j,s) = max(g(j-1,s-x[j])) + f[j](x[j]) for x[j]=0 to s) 

這可以有效地通過計算g作爲表來解決：

g(0,s) = 0 
g(1,s) = max(g(0,s-x1) + f1(x1) for x1=0 to s) 
g(2,s) = max(g(1,s-x2) + f2(x2) for x2=0 to s) 
etc.