动态规划方法

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.