Dynamic Programming and Backtracking.pptx

DP is an optimization over plain recursion
DP optimizes repeated calls for same inputs
Results of subproblems are stored to avoid recomputation, hence time complexity reduces from exponential to polynomial
Properties:
Overlapping Subproblems : Solutions of same subproblems are needed again and again
Optimal Substructure : Optimal solution of the given problem can be obtained by using optimal solutions of its subproblems

There are following two different ways to store the values so that these values can be reused: 
�a) Memoization (Top Down) 
�b) Tabulation (Bottom Up)

1. Unit-3 Dynamic Programming and Backtracking

2. Dynamic Programming DP is an optimization over plain recursion DP optimizes repeated calls for same inputs Results of subproblems are stored to avoid recomputation , hence time complexity reduces from exponential to polynomial Properties: Overlapping Subproblems  : Solutions of same subproblems are needed again and again Optimal Substructure  : Optimal solution of the given problem can be obtained by using optimal solutions of its subproblems

3. Fibonacci – Recursion vs DP Recursion int Fib ( int n) { if (n ≤ 1) return n; return Fib(n-1) + Fib(n-2); } Time Complexity:   T(n) = T(n-1) + T(n-2) which is exponential. DP F[0]=0; F[1]=1; for( i =2 ; i ≤ n ; i ++) F[ i ] = F[i-1] + F[i-2]; return F[n]; Time Complexity: O (n)

4. DP - Types There are following two different ways to store the values so that these values can be reused:  a) Memoization (Top Down)  b) Tabulation (Bottom Up)

5. Memoization (Top Down) It is similar to the recursive version with a small modification that it looks into a lookup table before computing solutions. Initial values of the lookup array is initialized with NIL. Whenever the solution to a subproblem is needed, first look into the lookup table. If the precomputed value is there then return that value, otherwise, calculate the value and put the result in the lookup table so that it can be reused later.

6. Memoization (Top Down) #include< stdio.h > #define NIL -1 #define MAX 100 int lookup[MAX]; void _initialize() { int i ; for ( i = 0; i < MAX; i ++) lookup[ i ] = NIL; } int fib( int n) { if (lookup[n] == NIL) { if (n <= 1) lookup[n] = n; else lookup[n] = fib(n-1) + fib(n-2); } return lookup[n]; } int main () { int n = 40; _initialize(); printf ("Fibonacci number is %d ", fib(n)); return 0; }

7. Tabulation (Bottom Up) The tabulated program for a given problem builds a table in bottom up fashion and returns the last entry from table. For example, for the same Fibonacci number, first calculate fib(0) then fib(1) then fib(2) then fib(3) and so on. So the solutions of subproblems is built bottom-up. 

8. Tabulation (Bottom Up) #include< stdio.h > int fib( int n) { int f[n+1]; int i ; f[0] = 0; f[1] = 1; for ( i = 2; i <= n; i ++) f[ i ] = f[i-1] + f[i-2]; return f[n]; } int main () { int n = 9; printf ("Fibonacci number is %d ", fib(n)); return 0; }

9. Steps to solve a DP Identify if it is a DP problem Decide a state expression with least parameters Formulate state relationship Do tabulation (or add memoization )

10. 0/1 Knapsack problem

11. 0/1 Knapsack problem using DP Without DP, using Recursion With DP Tabulation, using lookup table Memoization , using lookup table + Recursion

12. 0/1 Knapsack problem using Recursion K( remaining no. of items to choose , remaining available space ) refers to knapSack () wt [] = {1, 1, 1}, val [] = {10, 20, 30} W = 2

13. 0/1 Knapsack problem using Recursion Algorithm int knapsack (int wt [], int profit, int w, int N) { if (n ==0 || w ==0) //Base=Case return 0: if ( wt [n] > w) //Skip-case return knapsack ( wt , profit, w, N-1); else return Max ( Knapsack ( wt , profit, w, N-1) , profit [n] + Knapsack ( wt , profit, w- wt [n], N-1) ) ; } Time Complexity: 2 N

14. 0/1 Knapsack problem using Recursion #include < stdio.h > int max(int a, int b) { return (a > b) ? a : b; } int knapSack (int W, int wt [], int val [], int n) { if (n == 0 || W == 0) return 0; if ( wt [n - 1] > W) return knapSack (W, wt , val , n - 1); else return max( val [n - 1] + knapSack (W - wt [n - 1], wt , val , n - 1) , knapSack (W, wt , val , n - 1) ) ; } int main() { int val [3] = { 60, 100, 120 }; int wt [3] = { 10, 20, 30 }; int W = 50; int n; printf ("%d", knapSack (W, wt , val , n)); return 0; }

15. 0/1 Knapsack problem using Tabulation DP DP [5] [8] j  ( wt ) i (Items)

16. 0/1 Knapsack problem using Tabulation DP Algorithm int knapsack (int wt [], int profit, int w, int N) { for ( i =0 to N) for (j=0 to w) if ( i ==0 || j==0) dp [ i ][j]=0; else if ( wt [i-1] > j) dp [ i ][j] = dp [i-1][j]; else dp [ i ][j] = max ( dp [i-1][j] , profit [i-1]+ dp [i-1][w- wt [i-1]] ) return dp [N][w]; } Time Complexity: O (N . w)

17. 0/1 Knapsack problem using Tabulation DP #include < stdio.h > int max(int a, int b){ return (a > b) ? a : b; } int knapSack (int W, int wt [], int val [], int n) { int i , w; int K[n + 1][W + 1]; for ( i = 0; i <= n; i ++) { for (w = 0; w <= W; w++) { if ( i == 0 || w == 0) K[ i ][w] = 0; else if ( wt [ i - 1] <= w) K[ i ][w] = max( val [ i - 1] + K[ i - 1][w - wt [ i - 1]] , K[ i - 1][w] ) ; else K[ i ][w] = K[ i - 1][w]; } } return K[n][W]; } int main() { int val [3] = { 60, 100, 120 }; int wt [3] = { 10, 20, 30 }; int W = 50; int n = 3; printf ("%d", knapSack (W, wt , val , n)); return 0; }

18. 0/1 Knapsack problem using Memoization Algorithm int knapsack (int wt [], int profit, int w, int N) { if (n ==0 || w ==0) return 0: if ( dp [N][w] != -1) return dp [N][w]; int result; if ( wt [n] > w) result = knapsack ( wt , profit, w, N-1); else result = Max ( Knapsack ( wt , profit, w, N-1) , profit [n] + Knapsack ( wt , profit, w- wt [n], N-1) ) ; return dp [N][w] = result; } Time Complexity: O (N . w)