《算法课件全121301ADA15动态规划传递闭包与背包问题》由会员分享，可在线阅读，更多相关《算法课件全121301ADA15动态规划传递闭包与背包问题（50页珍藏版）》请在金锄头文库上搜索。
1、Dynamic Programming (II),Chapter 8,Application to graph problem Transitive Closure Application to Combinatorial Problem Knapsack Problem,2019/6/21,3,2012-2013-01 Design and Analysis of Algorithm SCUN,Transitive Closure Problem,0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0,0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 1,Definitio
2、n: The transitive closure of a directed graph with n vertices can be defined as the n-by-n boolean matrix T=tij, in which the elements in the ith row(1in) and the jth column (1jn) is 1 if there exists a nontrivial directed path from the ith vertex to the jth vertex; otherwise, tij=0.,Example,2019/6/
3、21,4,2012-2013-01 Design and Analysis of Algorithm SCUN,Warshalls Algorithm,Constructs transitive closure T as the last matrix in the sequence of n-by-n matrices R(0), , R(k), , R(n) where R(k)i,j = 1 iff there is nontrivial path from i to j with only first k vertices allowed as intermediate Note th
4、at R(0) = A (adjacency matrix), R(n) = T (transitive closure),R(0) 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0,R(1) 0 0 1 0 1 0 1 1 0 0 0 0 0 1 0 0,R(2) 0 0 1 0 1 0 1 1 0 0 0 0 1 1 1 1,R(3) 0 0 1 0 1 0 1 1 0 0 0 0 1 1 1 1,R(4) 0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 1,2019/6/21,5,2012-2013-01 Design and Analysis of Algor
5、ithm SCUN,Warshalls Algorithm (recurrence),On the k-th iteration, the algorithm determines for every pair of vertices i, j if a path exists from i and j with just vertices 1,k allowed as intermediate R(k-1)i,j (path using just 1 ,k-1) R(k)i,j = or R(k-1)i,k and R(k-1)k,j (path from i to k and from k
6、 to i using just 1 ,k-1),i,j,k,2019/6/21,6,2012-2013-01 Design and Analysis of Algorithm SCUN,Warshalls Algorithm (pseudocode and analysis),Warshall (W1n,1n) /Input: The adjacent matrix W of a digraph with n vertices /Output: The transitive closure matrix R of the digraph for i 1 to n do /initializa
7、tion for j 1 to n do Ri, j Wi, j for k 1 to n do for i 1 to n do for j 1 to n do Ri, j (Ri, j or (Ri, k and Rk, j) return R,Time efficiency: (n3),2019/6/21,7,2012-2013-01 Design and Analysis of Algorithm SCUN,Warshalls Algorithm (example),0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0,R(0) =,0 0 1 0 1 0 0,R(1) =,0
8、 1 0 1 1 0 1,R(2) =,0 0 1 0 1 0 1 1 0 0 0 0 1 1 1 1,R(3) =,0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 1,R(4) =,0,1,1,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,2019/6/21,8,2012-2013-01 Design and Analysis of Algorithm SCUN,Knapsack ProblemPresenting,Given a knapsack with maximum capacity W, and a set S consisting of n items
9、Each item i has some weight wi and benefit value vi (all wi , vi and W are integer values) Problem: How to pack the knapsack to achieve maximum total value of packed items?,2019/6/21,9,2012-2013-01 Design and Analysis of Algorithm SCUN,Knapsack ProblemPicturing,2019/6/21,10,2012-2013-01 Design and A
10、nalysis of Algorithm SCUN,（1）,（2）,Fractional Knapsack Problem,We can take fractions of items when we filled the items into the knapsack. Let xi (0xi1) denotes the parts which has been filled in the knapsack of item i. Then the fractional knapsack problem can be modeled as follows:,Search for a solut
11、ion vector X=(x1, x2, , xn) which satisfy the constraints condition (1) and max (2),2019/6/21,11,2012-2013-01 Design and Analysis of Algorithm SCUN,（1）,（2）,0/1 Knapsack Problem,Each item must be entirely accepted or rejected when we filled the item into the knapsack. Let xi (xi0,1) denotes whether i
12、tem i has been filled into knapsack or not. Then the 0/1 knapsack problem can be modeled as follows:,Search for a solution vector X=(x1, x2, , xn) which satisfy the constraints condition (1) and max (2),2019/6/21,12,2012-2013-01 Design and Analysis of Algorithm SCUN,Exhaustive SearchA Brute Force,Me
13、thod: generate a list of all potential solutions to the problem in a systematic manner evaluate potential solutions one by one, disqualifying infeasible ones and, for an optimization problem, keeping track of the best one found so far when search ends, announce the solution(s) found,2019/6/21,13,201
14、2-2013-01 Design and Analysis of Algorithm SCUN,Knapsack Problem by Exhaustive Search,Subset Total weight Total value 1 2 ￥20 2 5 ￥30 3 10 ￥50 4 5 ￥10 1,2 7 ￥50 1,3 12 ￥70 1,4 7 ￥30 2,3 15 ￥80 2,4 10 ￥40 3,4 15 ￥60 1,2,3 17 not feasible 1,2,4 12 ￥60 1,3,4 17 not feasible 2,3,4 20 not feasible 1,2,3,
15、4 22 not feasible,Efficiency: O(2n),Example: Knapsack capacity W=16 item weight value 1 2 ￥20 2 5 ￥30 3 10 ￥50 4 5 ￥10,2019/6/21,14,2012-2013-01 Design and Analysis of Algorithm SCUN,Dynamic Programming,We need to carefully identify the subproblems,Lets try this: If items are labeled 1n, then a subproblem would be to find an optimal so
