dynamic-programming - 动态规划的递归方程

Question

我的情况与背包问题非常相似，但我只想确认我的递归方程与背包问题相同。

我们最多可以投资 M 美元。我们有 N 个不同的投资，每一个都有成本 m(i) 和利润 g(i)。我们想找到最大化利润的递推方程。

这是我的答案：

     g(i,j) = max{g(i-1,j), g_i + (i-1,j-m_i)}      if j-m_i >= 0

              g(i-1,j)                              if j-m_i < 0

我希望我的解释清楚。

谢谢你，祝你有美好的一天！

鲍比

Answer 1

你的递归方程是正确的。该问题与传统的背包问题相同。其实你可以对空间复杂度做一些优化。这是 C++ 代码。

int dp[M + 10];
int DP{
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < N; ++i)
        for(int j = M; j >= m[i]; --j) // pay attention
            dp[j] = max(dp[j], dp[j - m[i]] + g[i]);
    int ret = 0;
    for(int i = 0; i <= M; ++i) ret = max(ret, dp[i]);
    return ret;
}