Rezidivgleichung für dynamische Programmierung - dynamische Programmierung

Ich habe eine Situation, die dem Rucksackproblem wirklich ähnlich ist, aber ich möchte nur bestätigen, dass meine Rekursionsgleichung die gleiche wie das Rucksackproblem ist.

Wir haben ein Maximum von M Dollar, um zu investieren. Wir haben N verschiedene Investitionen, die jeweils eine Kosten m (i) und einen Gewinn g (i) haben. Wir wollen die Rekursionsgleichung finden, um den Profit zu maximieren.

Hier ist meine Antwort:

     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

Ich hoffe meine Erklärung ist klar.

Danke und einen schönen Tag noch!

Bobby

Antworten:

Ihre Rekursionsgleichung ist korrekt. Das Problem ist dasselbe wie das traditionelle Rucksackproblem. Tatsächlich können Sie die Raumkomplexität optimieren. Hier ist der C ++ Code.

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