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