動態規劃的遞推方程

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 

我希望我的解釋是明確的。

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

Bobby

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; 
}