动态编程方法论

Question

我想知道你是否对一个问题有一些见解，我们考虑的是一个优化问题：

从j=1到fj( xj )中的n的最大j=1使得xj <=B中的∑到n中的∑

xj>=0，整数

其中B是正整数，fj是实数对实数

我正在尝试使用动态编程来制定一个解决方案，并计算出这种方法的时间复杂性。

我对动态编程方法有点困惑，如果使用n=5和B=10，如何为f1(x)=sqrt(x)这样的函数实现它

亲切的问候

Answer 1

你的问题是要解决

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.