dynamic - 动态规划方法

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.