Opakujúca rovnica pre dynamické programovanie - dynamické programovanie

Mám situáciu, ktorá je skutočne podobná problému s batohom, ale chcem len potvrdiť, že moja opakujúca sa rovnica je rovnaká ako problém s batohom.

Investujeme maximálne M dolárov. Máme N rôznych investícií, z ktorých každá má náklad m (i) a zisk g (i). Chceme nájsť rekurenčnú rovnicu pre maximalizáciu zisku.

tu je moja odpoveď:

     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

Dúfam, že moje vysvetlenie je jasné.

Ďakujem a prajem pekný deň!

polda

odpovede:

Vaša rovnica opakovania je správna. Problém je rovnaký ako problém tradičného batohu. V skutočnosti môžete urobiť nejakú optimalizáciu zložitosti priestoru. Tu je kód 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;
}