Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos, for i ← 2 to n do, F[i]← max(C[i] + F[i − 2], F[i − 1]),…
Algoritmos
Dynamic Programming
Sugere resolver cada um dos subproblemas menores apenas uma vez, registrando os resultados em uma tabela na qual uma solução para o problema original pode então ser obtida.
-
Change-making problem
//Input: Positive integer n and array D[1..m] of increasing positive integers indicating the coin denominations where D[1] = 1
-
Coin-collecting problem
//Input: Matrix C[1..n, 1..m] whose elements are equal to 1 and 0 for cells with and without a coin, respectively
-
-
-
-
F[i]← max(C[i] + F[i − 2], F[i − 1])
-
-
-
-
-
temp ← min(F[i − D[j ]], temp)
-
-
//Output: Largest number of coins the robot can bring to cell (n, m)
-
F[i, 1]← F[i − 1, 1] + C[i, 1]
-
F[i, j ]← max(F[i − 1, j ], F[i, j − 1]) + C[i, j ]
F[1, 1]← C[1, 1]; for j ← 2 to m do F[1, j ]← F[1, j − 1] + C[1, j ]
-
//Note: Uses as global variables input arrays W eights[1..n], V alues[1..n], and table F[0..n, 0..W] whose entries are initialized with −1’s except for row 0 and column 0 initialized with 0’s.
-
-
value ← MFKnapsack(i − 1, j)
-
value ← max(MFKnapsack(i − 1, j ), Values[i] + MFKnapsack(i − 1, j − Weights[i]))
-