Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dynamic programming, F[0]← 0; F[1]← C[1], Approximation Algorithms for NP…
Dynamic programming
Examples
Coin-row problem
There is a row of n coins whose values are some positive integers C0, C2, . . . , Cn-1, not necessarily distinct. The goal is to pick up the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up.
-
Change-making problem
The change-making problem addresses the question of finding the minimum number of coins (of certain denominations) that add up to a given amount of money. It is a special case of the integer knapsack problem, and has applications wider than just currency.
ALGORITHM ChangeMaking(D[1..m], n)
-
Coin-collecting problem
vSeveral coins are placed in cells of an n × m board, no more than one coin per cell. A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell.
-
principle of optimality
it's an optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances. The principle of optimality holds much more often than not.
-
-
-
-
F[i]← max(C[i] + F[i − 2], F[i − 1])
-
-
-
-
-
-
-
-
-
-
temp ← min(F[i − D[j ]], temp)
-
-
-
-
Step 3 Scan the vertex list obtained in Step 2 and eliminate from it all repeated occurrences of the same vertex except the starting one at the end of the list. (This step is equivalent to making shortcuts in the walk.) The vertices remaining on the list will form a Hamiltonian circuit, which is the output of the algorithm