- Knapsack Problem DP Solution
- Activity Selection Problem DP Solution
Dynamic Programming Algorithms
Dynamic programming is a fancy name for using divide-and-conquer technique with a table. As compared to divide-and-conquer, dynamic programming is more powerful and subtle design technique. Let me repeat , it is not a specific algorithm, but it is a meta-technique (like divide-and-conquer). This technique was developed back in the days when "programming" meant "tabular method" (like linear programming). It does not really refer to computer programming. Here in our advanced algorithm course, we'll also think of "programming" as a "tableau method" and certainly not writing code. Dynamic programming is a stage-wise search method suitable for optimization problems whose solutions may be viewed as the result of a sequence of decisions. The most attractive property of this strategy is that during the search for a solution it avoids full enumeration by pruning early partial decision solutions that cannot possibly lead to optimal solution. In many practical situations, this strategy hits the optimal solution in a polynomial number of decision steps. However, in the worst case, such a strategy may end up performing full enumeration.
Dynamic programming takes advantage of the duplication and arrange to solve each subproblem only once, saving the solution (in table or in a globally accessible place) for later use. The underlying idea of dynamic programming is: avoid calculating the same stuff twice, usually by keeping a table of known results of subproblems. Unlike divide-and-conquer, which solves the subproblems top-down, a dynamic programming is a bottom-up technique. The dynamic programming technique is related to divide-and-conquer, in the sense that it breaks problem down into smaller problems and it solves recursively. However, because of the somewhat different nature of dynamic programming problems, standard divide-and-conquer solutions are not usually efficient.
The dynamic programming is among the most powerful for designing algorithms for optimization problem. This is true for two reasons. Firstly, dynamic programming solutions are based on few common elements. Secondly, dynamic programming problems are typical optimization problems i.e., find the minimum or maximum cost solution, subject to various constraints.
In other words, this technique used for optimization problems:
- Find a solution to the problem with the optimal value.
- Then perform minimization or maximization. (We'll see example of both in CLRS).
The dynamic programming is a paradigm of algorithm design in which an optimization problem is solved by a combination of caching subproblem solutions and appealing to the "principle of optimality."
There are three basic elements that characterize a dynamic programming algorithm:
1. Substructure
Decompose the given problem into smaller (and hopefully simpler) subproblems. Express the solution of the original problem in terms of solutions for smaller problems. Note that unlike divide-and-conquer problems, it is not usually sufficient to consider one decomposition, but many different ones.
2. Table-Structure
After solving the subproblems, store the answers (results) to the subproblems in a table. This is done because (typically) subproblem solutions are reused many times, and we do not want to repeatedly solve the same problem over and over again.
3. Bottom-up Computation
Using table (or something), combine solutions of smaller subproblems to solve larger subproblems, and eventually arrive at a solution to the complete problem. The idea of bottom-up computation is as follow:
Bottom-up means
- Start with the smallest subproblems.
- Combining theirs solutions obtain the solutions to subproblems of increasing size.
- Until arrive at the solution of the original problem.
Once we decided that we are going to attack the given problem with dynamic programming technique, the most important step is the formulation of the problem. In other words, the most important question in designing a dynamic programming solution to a problem is how to set up the subproblem structure.
If I can't apply dynamic programming to all optimization problem, then the question is what should I look for to apply this technique? Well! the answer is there are two important elements that a problem must have in order for dynamic programming technique to be applicable (look for those!).
1. Optimal Substructure
Show that a solution to a problem consists of making a choice, which leaves one or sub-problems to solve. Now suppose that you are given this last choice to an optimal solution. [Students often have trouble understanding the relationship between optimal substructure and determining which choice is made in an optimal solution. One way to understand optimal substructure is to imagine that "God" tells you what was the last choice made in an optimal solution.] Given this choice, determine which subproblems arise and how to characterize the resulting space of subproblems. Show that the solutions to the subproblems used within the optimal solution must themselves be optimal (optimality principle). You usually use cut-and-paste:
- Suppose that one of the subproblem is not optimal.
- Cut it out.
- Paste in an optimal solution.
- Get a better solution to the original problem. Contradicts optimality of problem solution.
That was optimal substructure.
You need to ensure that you consider a wide enough range of choices and subproblems that you get them all . ["God" is too busy to tell you what that last choice really was.] Try all the choices, solve all the subproblems resulting from each choice, and pick the choice whose solution, along the subproblem solutions, is best.
We have used "Optimality Principle" a couple of times. Now a word about this beast: The optimal solution to the problem contains within it optimal solutions to subproblems. This is some times called the principle of optimality.
The Principle of Optimality
The dynamic programming relies on a principle of optimality. This principle states that in an optimal sequence of decisions or choices, each subsequence must also be optimal. For example, in matrix chain multiplication problem, not only the value we are interested in is optimal but all the other entries in the table are also represent optimal. The principle can be related as follows: the optimal solution to a problem is a combination of optimal solutions to some of its subproblems. The difficulty in turning the principle of optimally into an algorithm is that it is not usually obvious which subproblems are relevant to the problem under consideration.
Now the question is how to characterize the space of subproblems?
- Keep the space as simple as possible.
- Expand it as necessary.
As an example, consider the assembly-line scheduling. In this problem, space of subproblems was fastest way from factory entry through stations S1, j and S2, j. Clearly, no need to try a more general space of subproblems. On the hand, in case of optimal binary search trees. Suppose we had tried to constrain space of subproblems to subtrees with keys k1, k2, . . . , kj. An optimal BST would have root kr , for some 1 ≤ r ≤ j. Get subproblems k1, . . . , kr − 1 and kr + 1, . . . , kj. Unless we could guarantee that r = j, so that subproblem with kr + 1, . . . , kj is empty, then this subproblem is not of the form k1, k2, . . . , kj. Thus, needed to allow the subproblems to vary at both ends, i.e., allow both i and j to vary.
Optimal substructure varies across problem domains:
- How many subproblems are used in an optimal solution.
- How many choices in determining which subproblem(s) to use.
In Assembly-line Scheduling Problem: we have 1 subproblem and 2 choices (for Si, j use either S1, j − 1 or S2, j − 1). In the Longest Common Subsequence Problem: we have 1 subproblem but as far as choices are concern, we have either 1 choice (if xi = yj , LCS of Xi − 1 and Yj − 1), or 2 choices (if xi = yj , LCS of Xi − 1 and Y , and LCS of Xand Yj − 1). Finally, in case of the Optimal Binary Search Tree Problem: we have 2 subproblems (ki , . . . , kr − 1 and kr + 1, . . . , kj ) and j − i + 1 choices for kr in ki, . . . ,kj . Once we determine optimal solutions to subproblems, we choose from among the j − i + 1 candidates for kr .
Informally, the running time of the dynamic programming algorithm depends on the overall number of subproblems times the number of choices. For example, in theassembly-line scheduling problem, there are Θ(n) subproblems and 2 choices for each implying running time is Θ(n). In case of longest common subsequence problem, there are Θ(mn) subproblems and at least 2 choices for each implying Θ(mn) running time. Finally, in case of optimal binary search tree problem, we have Θ(n2) sub-problems and Θ(n) choices for each implying Θ(n3) running time.
Dynamic programming uses optimal substructure bottom up fashion:
- First find optimal solutions to subproblems.
- Then choose which to use in optimal solution to the problem.
When we look at greedy algorithms, we'll see that they work in top down fashion:
- First make a choice that looks best.
- Then solve the resulting subproblem.
Warning! You'll surely make an ass out of yourself into thinking optimal substructure applies to all optimization problems. IT DOES NOT. Let me repeat, dynamic programming is not applicable to all optimization problems.
To see this point clearly, go through pages 341 − 344 of CLRS where authors discussed two problems that look similar: Shortest Path Problem and Longest Simple Path Problem. In both problems, they gave us an unweighted, directed graph G = (V, E). And our job is to find finding a path (sequence of connected edges) from vertex u in Vto vertex v in V.
To see this point clearly, go through pages 341 − 344 of CLRS where authors discussed two problems that look similar: Shortest Path Problem and Longest Simple Path Problem. In both problems, they gave us an unweighted, directed graph G = (V, E). And our job is to find finding a path (sequence of connected edges) from vertex u in Vto vertex v in V.
Subproblems Dependencies
It is easy to see that the subproblems, in our above examples, are independent subproblems: For example, in the assembly line problem, there is only 1 subproblem so it is trivially independent. Similarly, in the longest common subsequence problem, again we have only 1 subproblem thus it is automatically independent. On the other hand, in the optimal binary search tree problem, we have two subproblems, ki, . . . , kr − 1 and kr + 1, . . . , kj, which are clearly independent.
2. Polynomially many (Overlapping) Subproblems
An important aspect to the efficiency of dynamic programming is that the total number of distinct sub-problems to be solved should be at most a polynomial number. Overlapping subproblems occur when recursive algorithm revisits the same problem over and over. A good divide-and-conquer algorithm, for example the merge-sort algorithm, usually generate a brand new problem at each stage of recursion. Our Textbook CLRS has a good example for matrix-chain multiplication to depict this idea. The CLRS also talked about the alternative approach so-called memoization. It works as follows:
- Store, don't recompute
- Make a table indexed by subproblem.
- When solving a subproblem:
- Lookup in the table.
- If answer is there, use it.
- Otherwise, compute answer, then store it.
In dynamic programming, we go one step further. We determine in what order we would want to access the table, and fill it in that way.
Four-Step Method of CLRS
Our Text suggested that the development of a dynamic programming algorithm can be broken into a sequence of following four steps.
- Characterize the structure of an optimal solution.
- Recursively defined the value of an optimal solution.
- Compute the value of an optimal solution in a bottom-up fashion.
- Construct an optimal solution from computed information.
Dynamic-Programming Solution
to the 0-1 Knapsack Problem
Problem Statement A thief robbing a store and can carry a maximal weight of W into their knapsack. There are n items and ith item weigh wi and is worth vidollars. What items should thief take?
There are two versions of problem
Fractional knapsack problem The setup is same, but the thief can take fractions of items, meaning that the items can be broken into smaller pieces so that thief may decide to carry only a fraction of xi of item i, where 0 ≤ xi ≤ 1.
0-1 knapsack problem The setup is the same, but the items may not be broken into smaller pieces, so thief may decide either to take an item or to leave it (binary choice), but may not take a fraction of an item.
Fractional knapsack problem
- Exhibit greedy choice property.
Þ Greedy algorithm exists. - Exhibit optimal substructure property.
- Þ
0-1 knapsack problem
- Exhibit No greedy choice property.
Þ No greedy algorithm exists. - Exhibit optimal substructure property.
- Only dynamic programming algorithm exists.
Dynamic-Programming Solution to the 0-1 Knapsack Problem
Let i be the highest-numbered item in an optimal solution S for W pounds. Then S` = S - {i} is an optimal solution for W - wi pounds and the value to the solution S isVi plus the value of the subproblem.
We can express this fact in the following formula: define c[i, w] to be the solution for items 1,2, . . . , i and maximum weight w. Then
0 if i = 0 or w = 0 c[i,w] = c[i-1, w] if wi ≥ 0 max [vi + c[i-1, w-wi], c[i-1, w]} if i>0 and w ≥ wi
This says that the value of the solution to i items either include ith item, in which case it is vi plus a subproblem solution for (i - 1) items and the weight excluding wi, or does not include ith item, in which case it is a subproblem's solution for (i - 1) items and the same weight. That is, if the thief picks item i, thief takes vi value, and thief can choose from items w - wi, and get c[i - 1, w - wi] additional value. On other hand, if thief decides not to take item i, thief can choose from item 1,2, . . . , i- 1 upto the weight limit w, and get c[i - 1, w] value. The better of these two choices should be made.
Although the 0-1 knapsack problem, the above formula for c is similar to LCS formula: boundary values are 0, and other values are computed from the input and "earlier" values of c. So the 0-1 knapsack algorithm is like the LCS-length algorithm given in CLR for finding a longest common subsequence of two sequences.
The algorithm takes as input the maximum weight W, the number of items n, and the two sequences v = <v1, v2, . . . , vn> and w = <w1, w2, . . . , wn>. It stores the c[i, j] values in the table, that is, a two dimensional array, c[0 . . n, 0 . . w] whose entries are computed in a row-major order. That is, the first row of c is filled in from left to right, then the second row, and so on. At the end of the computation, c[n, w] contains the maximum value that can be picked into the knapsack.
Dynamic-0-1-knapsack (v, w, n, W)
FOR w = 0 TO W
DO c[0, w] = 0
FOR i=1 to n
DO c[i, 0] = 0
FOR w=1 TO W
DO IFf wi ≤ w
THEN IF vi + c[i-1, w-wi]
THEN c[i, w] = vi + c[i-1, w-wi]
ELSE c[i, w] = c[i-1, w]
ELSE
c[i, w] = c[i-1, w]
The set of items to take can be deduced from the table, starting at c[n. w] and tracing backwards where the optimal values came from. If c[i, w] = c[i-1, w] item i is not part of the solution, and we are continue tracing with c[i-1, w]. Otherwise item i is part of the solution, and we continue tracing with c[i-1, w-W].
Analysis
This dynamic-0-1-kanpsack algorithm takes θ(nw) times, broken up as follows: θ(nw) times to fill the c-table, which has (n +1).(w +1) entries, each requiring θ(1)time to compute. O(n) time to trace the solution, because the tracing process starts in row n of the table and moves up 1 row at each step.
Dynamic-Programming Algorithm
for the Activity-Selection Problem
An activity-selection is the problem of scheduling a resource among several competing activity.
Problem Statement Given a set S of n activities with and start time, Si and fi, finish time of an ith activity. Find the maximum size set of mutually compatible activities.
Compatible Activities
Activities i and j are compatible if the half-open internal [si, fi) and [sj, fj) do not overlap, that is, i and j are compatible if si ≥ fj and sj ≥ fi
Dynamic-Programming Algorithm
The finishing time are in a sorted array f[i] and the starting times are in array s[i]. The array m[i] will store the value mi, where mi is the size of the largest of mutually compatible activities among activities {1, 2, . . . , i}. Let BINARY-SEARCH(f, s) returns the index of a number i in the sorted array f such that f(i) ≤ s ≤ f[i + 1].for i =1 to n
do m[i] = max(m[i-1], 1+ m [BINARY-SEARCH(f, s[i])])
We have P(i] = 1 if activity i is in optimal selection, and P[i] = 0
otherwise
i = n
while i > 0
do if m[i] = m[i-1]
then P[i] = 0
i = i - 1
else
i = BINARY-SEARCH (f, s[i])
P[i] = 1
Analysis
The running time of this algorithm is O(n lg n) because of the binary search which takes lg(n) time as opposed to the O(n) running time of the greedy algorithm. This greedy algorithm assumes that the activities already sorted by increasing time.
0 comments