algorithm - 使用动态规划最小化函数

Question

如何最小化函数 y₁² + y₂² + ... + y_n² 约束 y₁*y₂*...*y_n = C; y₁,y₂,...,y_n> 0 使用动态规划？我试图解决这个问题，但我不知道如何创建循环函数。

Answer 1

你需要思考如何将问题缩小为“更小的问题”

D(i,c) = min { D(i-1, c/y) + y^2 | 1 <= y <= c }

在上面，您将问题从 y1,y2,....,yi 简化为 y1,...,y_{i-1}，并检查 y_i 所有可能的分配 - 并从中选择最好的。

基本条款将是:

D(0,0) = 0
D(i,0) = Infinity    i>0

假设 i,c 是整数，您可以使用这些递归公式进行自上而下或自下而上的 DP 解决方案。 (可能需要添加 D(i,c) = Infinity if c is not natural

的停止子句