Dynamic Programming


Dynamic programming solves problem by combining the solutions of different sub problem. It is the techniques that is used in optimization.

Dynamic programming algorithm, it is a techniques of reuse of problem which already solved.

Properties of Dynamic programming Strategies.

1) Overlapping Sub-problems – Means combines solutions to sub-problems.

2) Optimal Sub-Structure – Optimal solutions of the given problem can be obtained using optimal solutions of its sub-problem.

Ways to solve problem Using Dynamic Programming.

1) Top-down.

2) Bottom-Up.

Top-down: In this process the given problem has to solve by breaking it down. If you see that the problem has already been solved, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This property is referred as Memoization.

Bottom-up: Analyse the problem and see the order in which the sub-problems are solved and start solving from trivial sub-problems.

In this process it is guaranteed that the sub-problems are solved before solving the problem. This is known as Dynamic Programming.

Let us see an example that will help us to understand the Algorithm.

Knapsack Problem.

In 0-1 Knapsack, Items cannot be broken which means the thief should take the item as a whole or should leave it. As it is called 0-1 knapsack.

Hence in case of 0-1 knapsack, the value of xi can be either 0 or 1. Where other constraints remain the same.

0-1 Knapsack cannot solved by greedy algorithm approach, it does not ensure as optimal solutions.

Item    A  B  C D

Profit - 24 18 18 10

Weight - 24 10 10 7

Let us consider that the capacity of the Knapsack is W=25 and the items are as shown in the following items.

Solutions – Without considering the profit per unit weight (pi/wi), if we apply Greedy approach to solve this problem, first item A will be selected as it will contribute maximum profit among all the element.

After selecting the item A, no more item will be selected hence for the given set of items total profit is 24. Whereas, the optimal solutions can be achieved by selecting items, B and C, where the total profit is 18+18=36.

- EduWithUs Team.