Explain in brief about the Dynamic Programming Approach for algorithm design. How it differs with recursion? Explain the algorithm for solving the 0/1 Knapsack problem using the dynamic programming approach and explain its complexity.

Question

Suresh Chand · Accepted Answer

The dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-problems are not solved independently. Rather, the results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems. Dynamic programming is used where we have problems, which can be divided into similar sub-problems so that their results can be re-used. Mostly, these algorithms are used for optimization. Before solving the in-hand sub-problem, the dynamic algorithm will try to examine the results of the previously solved sub-problems. The solutions of sub-problems are combined in order to achieve the best solution. Characteristics: Dynamic Programming works when a problem has the following features: Optimal Structure: If an optimal solution contains optimal visit solutions then a problem exhibits optimal substructure. Overlapping sub-problems: When a recursive algorithm would visit the same sub-problems repeatedly, then a problem has overlapping sub-problems. If the problem has an optimal substructure, then we can recursively define an optimal solution. If a problem has overlapping sub-problems, then we can improve on implementation by computing each sub-problem only once. Difference Between Dynamic Programming && Recursion: With respect to iteration, recursion has the following advantages and disadvantages: Simplicity: often a recursive algorithm is simple and elegant compared to an iterative algorithm Space-inefficiency: every recursive call adds a layer to the system’s call stack. If the number of stacked recursive calls gets too large, the result is a stack overflow. Every recursive algorithm can be implemented iteratively. 0/1 Knapsack Problem: The 0/1 knapsack problem means that the items are either complete or no items are filled in a knapsack. For example, we have two items having weights of 2kg and 3kg, respectively. If we pick the 2kg item then we cannot pick the 1kg item from the 2kg item (the item is not divisible); we have to pick the 2kg item completely. This is a 0/1 knapsack problem in which either we pick the item completely or we will pick that item. The 0/1 knapsack problem is solved by dynamic programming. Let W = capacity of Knapsack n = No. of items w = [w1, w2, w3, . . . . wn] = weight of items V = [v1, v2, . . . vn] = value of items C[i, w] = maximum profit earned with item i and with knapsack of capacity w Then the recurrence relation for 0/1 knapsack problem is given as, (C[i, w] = begin{bmatrix} 0 & if = 0 enspace or enspace w = 0 C[i-1, w] & if enspace wi > w Max[vi + C[i-1, w-wi], c[i-1, w]] & if enspace i > 0 enspace and enspace wi leq w end{bmatrix}) Algorithm: DynaKnapsack(W, n, v, w){ for(w=0; w<=W; w++){ C[0, w] = 0; for(i=0; i<=n; i++) C[i, w] = 0; for(i = 1; i <= n; i++){ for( w = 1; w <= W; w++ ){ if( w[i] < w ){ if( v[i] + C[i-1, w-W[i]] > C[i-1, w] ) C[i, w] = v[i] + C[i-1, w-w[i]]; else C[i, w] = C[i-1, w]; }else{ C[i, w] = C[i-1, w]; } } } } } Analysis: For run time analysis examining the above algorithm the overall run time of the algorithm is O(nW)

Explain in brief about the Dynamic Programming Approach for algorithm design. How it differs with recursion? Explain the algorithm for solving the 0/1 Knapsack problem using the dynamic programming approach and explain its complexity.

Leave your Answer:

Hits Counter

Question

Explain in brief about the Dynamic Programming Approach for algorithm design. How it differs with recursion? Explain the algorithm for solving the 0/1 Knapsack problem using the dynamic programming approach and explain its complexity.

Leave your Answer: