Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dynamic Programming - Coggle Diagram
Dynamic Programming
-
-
Coin-row problem
There is a row of n coins whose values are some positive integers c1, c2, ..., cn not necessarily distinct. Goal: pick up the maximum amount of money, but not picking up two adjacent coinsRecurrence relation:
- F(n) = max{cn + F(n − 2), F(n − 1)}, for n > 1
- F(0) = 0 e F(1) = c1
Algorithm: int CoinRow(C[1..n])
- F[0], F[1] ← 0, C[1];
for i ← 2 to n do
- ----F[i] ← max(C[i] + F[i − 2], F[i − 1]);
- return F[n];
-
Change-making problem
Give change for amount n using the minimum number of coins d1 < d2 < ... < dm where d1 = 1 (assuming unlimited coins)Recurrence relation:
- F(n) = minj:n≥dj {F(n − dj)} + 1, para n > 0
- F(0) = 0
Algorithm: int ChangeMaking(D[1..m], n)
- F[0] ← 0;
- for i ← 1 to n do
- ----temp, j ← ∞, 1;
- ----while j ≤ m ∧ i ≥ D[j] do
- --------temp ← min(F[i − D[j]], temp);
- --------j ← j + 1;
- ----F[i] ← temp + 1;
- return F[n];
-
Knapsack (0-1)
Given n items of weight wi and value vi, where i = 1 · · · n, and a capacity W, find the most valuable subset of items that fits into the knapsack’s capacityRecurrence relation:
- F(i, j) = max{F(i − 1, j), vi + F(i − 1, j − wi)}, if j − wi ≥ 0
- F(i, j) = F(i − 1, j), if j − wi < 0
- F(0, j) = 0, for j ≥ 0, F(i, 0) = 0, for i ≥ 0
Example: knapsack (0-1) – bottom-up5 
Algorithm: int Knapsack(n,W,w[1..n],v[1..n],F[0..n,0..W])
- for i ← 0 to n do
- ----for j ← 0 to W do
- --------if i = 0 ∨ j = 0 then F[i][j] ← 0;
- --------else if w[i] ≤ j then
- ------------F[i][j] ← max(F[i − 1][j], v[i] + F[i − 1][j − w[i]]) ;
- --------else F[i][j] ← F[i − 1][j] ;
- return F[n][W];
Example: knapsack (0-1) – top-down | 0,j/i,0=0, i,j=-1 Algorithm: int MFKnapsack(i,j,w[1..n],v[1..n],F[0..n,0..W])
- if F[i, j] < 0 then
- ----if j < w[i] then value ← MFKnapsack(i − 1, j, w, v, F) ;
- ----else
- --------value ← max(MFKnapsack(i − 1, j, w, v, F), v[i] + MFKnapsack(i − 1, j − w[i], w, v, F);
- ----F[i, j] ← value;
- return F[i, j];
Approximation algorithms
Sometimes it is even harder to find a solution
Alternative: “solve” the problem using approximation algorithms
- The solution does not need to be optimal, but only acceptable
Examples: greed approximation for TSP
- Nearest-neighbour algorithm
- MST-based algorithm
TSP: nearest-neighbour algorithm
Initial node: a
- sa = a − b − c − d − a, cost = 10
Optimal solution
- s∗ = a − b − d − c − a, cost = 8
- Accuracy ration: r(sa) = 10 / 8 = 1, 25
Changing the weight of (a, d) to w:
TSP: MST-based algorithm
In general terms:
- Construct an MST
- Perform a walk around the MST (recording the order of nodes visited)
- Eliminate all repeated occurrences except the initial node (making shortcuts in a walk)
-