Dynamic Programming Algorithm

Hello Everyone !!

After very long break welcome back to the “Shelf of Algorithm” , Without wasting time lets start with next type before going to next type just recall all basic concepts which I have share with you in previous blog.

Basics:

A dynamic programming algorithm remembers past results and uses them to find new results. Dynamic programming is similar to the Divide and Conquer 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. It can be solved by using both method that is Top-down and Bottom-up. Without going for proper definition we will see the examples which can be solved by using the dynamic programming.

Examples:

Dynamic programming is generally used for optimization problems. The Following computer problems can be solved by using the dynamic programming.

• Fibonacci number series
• Knapsack problem
• Tower of Hanoi
• All pair shortest path by Floyd-War shall
• Shortest path by Dijkstra
• Project scheduling

We will see and discuss the all important examples which will ask during the interviews in the further blog series of Interview Questions . To get the clear idea about this type lets see one example of 0-1 Knapsack problem asked in the Interview.

Example: Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item or don’t pick it (0-1 property).

Solution:

<code>

1. #include <stdio.h>
2.  
3. int max(int a, int b) { return (a > b)? a : b; }
4. // Returns the maximum value that can be put in a knapsack of capacity W
5. int knapsack(int W, int wt[], int val[], int n)
6. {
7. int i, w;
8. int K[n+1][W+1];
9.  
10. // Build table K[][] in bottom up manner
11. for (i = 0; i <= n; i++)
12. {
13. for (w = 0; w <= W; w++)
14. {
15. if (i==0 || w==0)
16. K[i][w] = 0;
17. else if (wt[i-1] <= w)
18. K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
19. else
20. K[i][w] = K[i-1][w];
21. }
22. }
23.  
24. return K[n][W];
25. }
26.  
27. int main()
28. {
29. int val[] = {60, 100, 120};
30. int wt[] = {10, 20, 30};
31. int W = 50;
32. int n = sizeof(val)/sizeof(val[0]);
33. printf(“\nValue = %d”, knapsack(W, wt, val, n));
34. return 0;
35. }

</code>

Output:

<code>

$ gcc knapsack.c -o knapsack
$ ./knapsack
 
Value = 220

</code>

Note: Above function computes the same sub-problems again and again.

Solve the problems as much as to get the best output for your struggle as an input, Till then stay tuned stay connected to know about the next type. I’ll come back with next blog and next type within a few hours.