Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dynamic Programming, Approximation Algorithms, It does not have to be…
-
-
-
is a technique for solving problems with overlapping subproblems. Rather than solving overlapping subproblems again and again, dynamic programming suggests solving each of the smaller subproblems only once and recording the results in a table which solution to the original problem can then. be obtained
-
-
-
- Change-making problem (F(n) = min {F(n-d[j])} + 1 for n > 0, j: n ≥ d[j])
- Coin-collecting problem (F(i, j) = max{F(i-1, j), F(i, j-1)} + c[i][j] for 1 ≤ i ≤ n, *1 ≤ j ≤ m)
- Knapsack (F(i, j) = max{F(i-1, j), v[I] + F(i-1, j-w)} if j - w[I] ≥ 0 AND F(i, j) = F(i-1, j) if *j-w[i] < 0)
- Fibonacci (F(n) = F(n-1) + F(n-2) for n > 1)
- Coin-row problem (F(n) = max {Cn + F(n-2), F(n-1)} for n > 1)
-
this method solves a given problem in the top-down manner but, in addition, maintains a table of the kind that would gave been used by a bottom-up dynamic programing algorithm
generally associated with NP-Hard problems, they do not necessarily produce an optimal solution, but solutions that are within a certain factor of the optimal solution.
-
-
-
-
- Nearest-Neighbour Algorithm
-
-