application of dynamic programming.pptx

Dynamic programming in DAA

1. Shri sai college of engineering and technology DBATU UNIVERSITY BRANCH :- COMPUTER SCIENCE & TECHNOLOGY SESSION :-2023-24 PRESENTED BY:- DEEPA .R. BAIRAGI

2. APPLICATION OF DYNAMIC PROGRAMMING

3. Applications are :- 0/1 knapsack problem Mathematical optimization problem Shortest path problem Reliability design problem Longest common subsequence (LCS) Flight control and robotics control Time sharing: It schedules the job to maximize CPU usage

4. Knapsack problem :- The knapsack problem states that − given a set of items, holding weights and profit values, one must determine the subset of the items to be added in a knapsack such that, the total weight of the items must not exceed the limit of the knapsack and its total profit value is maximum.

5. Examples:- Item 1: Weight = 2, Value = 10 Item 2: Weight = 3, Value = 5 Item 3: Weight = 5, Value = 15 Item 4: Weight = 7, Value = 7 Item 5: Weight = 1, Value = 6 V(i, W) = max { V(i-1, W), V(i-1, W - w[i]) + v[i] } W 1 2 3 4 5 6 7 8 9 10 Item1 10 10 10 10 10 10 10 10 10 Item2 10 10 10 15 15 15 15 15 15 Item3 10 10 10 15 15 15 15 15 20 Item4 10 10 10 15 15 17 17 17 22 Item5

6. Shortest path problem   T he shortest path problem is  the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized .

7. Mathematical optimization problem :- Dynamic programming is a powerful technique for solving optimization problems by breaking them down into smaller overlapping subproblems and efficiently solving them. It is especially useful when there are overlapping subproblems and optimal solutions to larger problems can be built from optimal solutions to smaller subproblems.

8. Reliability problem :- Reliability means the ability of an apparatus, machine, or system to consistently perform its intended or required function or mission, on demand and without degradation or failure. Reliability design using dynamic programming is used to solve a problem with a multiplicative In  reliability design , the problem is to design a system that is composed of several devices connected in series.

9. Longest common subsequence (LCS) The longest common subsequence (LCS) is defined as the longest subsequence that is common to all the given sequences, provided that the elements of the subsequence are not required to occupy consecutive positions within the original sequences.

10. Flight control and robotics control :- FLIGHT CONTROL :- flight control, dynamic programming can be utilized for tasks such as trajectory planning, path optimization, and control system design. By formulating the problem as an optimization task, dynamic programming algorithms can effectively search for the optimal solution.

11. robotics control :- I n robotics control, dynamic programming techniques can be applied to achieve tasks such as motion planning, path optimization, and manipulation. By considering the robot's dynamics, environment constraints, and objectives, dynamic programming can assist in generating optimal control policies.

12. Thank you