Dynamic Programming PDF
Document Details
Tags
Summary
These notes give an overview of dynamic programming, comparing and contrasting it with Divide and Conquer and Greedy algorithms. They also discuss the principle of optimality and its application in multi-stage graphs and the 0/1 knapsack problem.
Full Transcript
Dynamic Programming Dynamic Programming Dynamic programming is applied to optimization problems. Solve problems with overlapping subproblems. Each subproblem solved only once and result recorded in a table. Divide and Conquer Vs Dynamic Programming Divide and Conquer...
Dynamic Programming Dynamic Programming Dynamic programming is applied to optimization problems. Solve problems with overlapping subproblems. Each subproblem solved only once and result recorded in a table. Divide and Conquer Vs Dynamic Programming Divide and Conquer Dynamic Programming Subproblems are independent Subproblems are overlapping Recomputations performed No need to recompute Less efficient due to rework More efficient Recursive method (Top down approach of problem Iterative method(Bottom up approach of problem solving solving Splits its input at specific deterministic points usually in Splits its input at every possible split point middle Greedy Vs Dynamic Programming Greedy Dynamic Programming Used to obtain optimum solution Also obtains optimum solution Picks optimum solution from a set of feasible solution No special set of feasible solution Optimum selection is without revising previously Consider all possible sequences to obtain possible generated selection solution Only decision sequence is ever generated selection Many decision sequence may be generated No guarantee of getting optimum solution Guarantee of getting optimum solution using Principal of optimality Principle of Optimality Principle of Optimality: suppose that in solving a problem, we have to make a sequence of decisions D1,D2……..Dn. If this sequence is optimal, then the last k decisions, 1
