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 something) 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.
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.
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.
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 vi dollars. 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 is Vi 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 =
Dynamic-0-1-knapsack (v, w, n, W)
FOR w = 0 TO W DO c[0, w] = 0FOR 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.
No comments:
Post a Comment