Bài giảng Dynamic Programming

Dynamic Programming 2013-09-22 Dao Thanh Tinh 2 Introduction Quy hoạch động:  Thường dùng để giải các bài toán tối ưu;  Phân rã bài toán thành các bài toán con; hình thành lời giải từ các bài toán con;  Lưu trữ lời giải các bài toán con trong một bảng dữ liệu thay cho giải lại các bài toán con (đệ quy). Đặc điểm của phương pháp chia để trị: •Thường phát sinh các bài toán con “mới” •Lời giải các bài toán con thường được sử dụng nhiều lần (“phủ chồng”). 2013-09-22 Dao Thanh Tinh 3 Introduction (2) Ví dụ 1: Tính số Fibonacci thứ n với f0=0 và f1 = 1 Đệ quy: long f(int m) { if (n==0) return 0; else if (n==1) return 1; else return f(n-1) + f(n); } Ví dụ, để tính f(n) phải tính f(2) n-1 lần! Dùng mảng: f[0] = 0; f[1]=1; for (i=2; in;i++) f[i] = f[i-1] + f[i-2]; output f[n]; 5 2 51 2 51 nn fn                    Theo công thức: Tiết kiệm bộ nhớ: f0 = 0; f1=1; for (i=2; in;i++) { tg = f1 + f0; f0 = f1; f1 = tg; } output f1; 2013-09-22 Dao Thanh Tinh 4 Introduction (3) Số Fibonacci thứ n n=50 F(n) =12,586,269,025 Phương pháp đệ quy 650 800s Các phương pháp khác 1s 2013-09-22 Dao Thanh Tinh 5 Introduction (4) Tiếp cận theo hướng bottom-up 1. Xuất phát từ những bài toán cơ sở có lời giải (cách giải đơn giản hoặc có sẵn) 2. Từ tập lời giải các bài toán con tìm lời giải của bài toán lớn hơn. 2013-09-22 Dao Thanh Tinh 6 Introduction (5) PRINCIPLE OF OPTIMALITY “An optimal policy has the property that whatever the initial state and initial decisions are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decisions.” Richard Bellman “The Theory of Dynamic Programming”, Bulletin of the American Mathematical Society, Vol. 60, No. 6, 1954 (503-515). 2013-09-22 Dao Thanh Tinh 7 Introduction (6) Một chiến lược tối ưu có đặc trưng: với mọi trạng thái khởi tạo và quyết định ban đầu, các quyết định tiếp theo phải thiết lập được chiến lược tối ưu đối với trạng thái được hình thành từ các quyết định trước đó. Chiến lược tối ưu: có thể trong một số bước đầu tiên lựa chọn dường như không tốt nhưng tổng hợp cả quá trình phải tốt nhất. 2013-09-22 Dao Thanh Tinh 8 Introduction (7) Kỹ thuật giải bài toán bằng phương pháp QHĐ: a) Bắt đầu với những trường hợp con nhỏ nhất (thường là đơn giải nhất và giải được ngay). b) Tổ hợp các kết quả đã có (không phải tính lại) của các trường hợp con, sẽ đạt đạt tới kết quả của trường hợp có kích thước lớn và tổng quát hơn, cho đến khi cuối cùng đạt tới lời giải của bài toán ban đầu. 2013-09-22 Dao Thanh Tinh 9 Introduction (8) Xét bài toán: Cho túi T có sức chứa 10kg và 3 đồ vật: 1) 5kg, trị giá 4$ 2) 4kg, trị giá 10$ 3) 6kg, trị giá 3$ Xếp những đồ vật nào vào túi để có giá trị lớn nhất? Ví dụ 2: 2013-09-22 Dao Thanh Tinh 10 Introduction (9) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0!!!! 0 9 00000000000 10876543210đv Giá trị lớn nhất của túi: 2013-09-22 Dao Thanh Tinh 11 Introduction (10) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1 000000000000 4 9 44444000001 10876543210đv Giá trị lớn nhất của túi: 2013-09-22 Dao Thanh Tinh 12 Introduction (11) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1,2 444444000001 000000000000 14 9 14101010101000002 10876543210đv Giá trị lớn nhất của túi: 2013-09-22 Dao Thanh Tinh 13 Introduction (12) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1,2,3 1414101010101000002 444444000001 000000000000 14 9 14101010101000003 10876543210đv Giá trị lớn nhất của túi: 2013-09-22 Dao Thanh Tinh 14 Introduction (12) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1,2,3 1414101010101000002 444444000001 000000000000 14 9 14101010101000003 10876543210đv Giá trị lớn nhất của túi: Lời giải: Xếp vật 1, 2; tổng trọng lượng đồ vật là 9, giá trị là 14. 2013-09-22 Dao Thanh Tinh 15 Introduction (13) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0!!!! 0 9 00000000000 10876543210đv Giá trị lớn nhất của túi: Ví dụ 3: T = 10kg, a1={6kg, 5$}, a2={4kg, 4$}, a3={4kg, 10$} 2013-09-22 Dao Thanh Tinh 16 Introduction (14) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1 000000000000 5 9 55550000001 10876543210đv Giá trị lớn nhất của túi: Ví dụ 3: T = 10kg, a1={6kg, 5$}, a2={4kg, 4$}, a3={4kg, 10$} 2013-09-22 Dao Thanh Tinh 17 Introduction (15) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1,2 555550000001 000000000000 5 9 95554400002 10876543210đv Giá trị lớn nhất của túi: Ví dụ 3: T = 10kg, a1={6kg, 5$}, a2={4kg, 4$}, a3={4kg, 10$} 2013-09-22 Dao Thanh Tinh 18 Introduction (16) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1,2,3 955554400002 555550000001 000000000000 14 9 15141010101000003 10876543210đv Giá trị lớn nhất của túi: Ví dụ 3: T = 10kg, a1={6kg, 5$}, a2={4kg, 4$}, a3={4kg, 10$} 2013-09-22 Dao Thanh Tinh 19 Introduction (17) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1,2,3 955554400002 555550000001 000000000000 14 9 15141010101000003 10876543210đv Giá trị lớn nhất của túi: Lời giải: Xếp vật 1, 3; tổng trọng lượng đồ vật là 10, giá trị là 15. Ví dụ 3: T = 10kg, a1={6kg, 5$}, a2={4kg, 4$}, a3={4kg, 10$} 2013-09-22 Dao Thanh Tinh 20 Introduction (18) Example 1. An Allocation Problem. Giả thiết x>0 là giá trị đầu tư ở thời điểm ban đầu. Chia x thành 2 phần: y0 và x-y 0 Khai thác: phần thứ nhất mang lại g(y), giá trị còn lại là ay, 0<a<1; phần thứ hai mang lại h(x-y), giá trị còn lại là b(x-y), 0<b<1; Quá trình khai thác tiếp tục với ay+b(x-y) cho đến khi có thể kết thúc. Hỏi, ở mỗi bước cần phân chia như thế nào để đạt giá trị lớn nhất. Kí hiệu f(x) là giá trị thu được khi khai thác tốt nhất lượng đầu tư x ban đầu f(x) = sup {g(y) + h(x - y) + f (ay + b(x - y)) }, 0yx, f(0) = 0 2013-09-22 Dao Thanh Tinh 21 Introduction (19) Example 2. Stochastic Gold Mining Giả thiết: 2 mỏ vàng A, B và một máy khai thác vàng rất nhạy: Nếu khai thác ở mỏ A: xác suất p là khai phá được r% lượng quặng máy vẫn chưa hỏng, xác suất (1-p) là không được gì và máy hỏng. Sử dụng ở mỏ B: s% với xác suất q và máy không bị hỏng, xác suất (1-q) không tìm được vàng và hỏng máy. Ở mỗi giai đoạn, chừng nào máy chưa hỏng có thể chọn khai thác ở mỏ A hay B. Cho trước lượng quặng x và y ở mỏ A và B tương ứng. Chọn trình tự khai thác tối ưu. Ký hiệu f(x, y) là lượng quặng đào được tối đa trước khi máy bị hỏng. Hiệu quả khai thác ở mỏ A: p(rx + f((1r)x, y)) Hiệu quả khai thác ở mỏ B: q(sy + f(x, (1s)y)) f(x,y) = rx + f((1  r)x,y), if p[rx + f((1r)x, y)]  q[sy + f(x, (1s)y)] =sy + f(x, (1s)y), othewise 2013-09-22 Dao Thanh Tinh 22 Matrix Multiplication Problem Suppose given matrices A1, A2,...,An, where the dimensions of Ai is di-1di How should compute A1A2... An What is the minimum number of element-wise multiplications? 2013-09-22 Dao Thanh Tinh 23 Matrix Multiplication (2) Example 1 A  B  C 401 140 4010 Cho A kích thước mn B kích thước np Tính C = AB C(i,j) = A(i,1)*B(1,j) + A(I,2)*B(2,j) ++ A(I,n)*B(n,j) i = 1,..m, j = 1,..p Số phép nhân: mnp A(BC) 401 110 40.1.10 + 1.40.10 = 800 (AB)C 4040 4010 40.1.40 + 40.40.10 = 32,000 2013-09-22 Dao Thanh Tinh 24 Matrix Multiplication (3) Example 2 10504010140401 DCBA (AB) (CD) [(AB) C] D [A (BC)] D A [(BC) D] A [B (CD)] 2013-09-22 Dao Thanh Tinh 25 Matrix Multiplication (4) Example 2 10504010140401 DCBA 24,000T=AP: 4050 40*50=2000 P=BM: 150 40*50 = 2,000 M=CD: 4050 10*50*40=20,000 A [ B (CD) ] 2,900T=AP: 4050 40*50=2,000 P=MD: 150 10*50 = 500 M=BC: 110 1*40*10=400 A [ (BC) D ] 40,800T=PD: 4050 20*50*40=40,000 P=AM: 4010 40*10 = 400 M=BC: 110 1*40*10=400 [ A (BC) ] D 57,600T=PD: 4050 20*50*40=40,000 P= MC: 4010 40*10*40=16,000 M=AB: 4040 40*40=1,600 [(AB) C ] D 101,600T= MP: 40x50 40*50*40=80,000 P = CD: 40x50 10*50*40=20,000 M = AB: 40x40 40*40=1,600 (AB) (CD) 2013-09-22 Dao Thanh Tinh 26 Matrix Multiplication (5) Ký hiệu Mij = Ai  Ai+1  ...  Aj-1  Aj , i  j B[i, j] = số ít nhất phép nhân để tính Mij B[1,n] - số ít nhất phép nhân để tính A1A2... An 2013-09-22 Dao Thanh Tinh 27 Matrix Multiplication (6) Suppose Mij = (AiAi+1... Ak)(Ak+1...Aj-1Aj) B[i, j]k = B[i,k] + di-1dkdj + B[k+1,j] B[i, j] = min { B[i, j]k: i  k < j } = min { B[i,k] + di-1dkdj + B[k+1,j] } 2013-09-22 Dao Thanh Tinh 28 Matrix Multiplication (7) Mij = (AiAi+1... Ak)(Ak+1...Aj-1Aj) B[i, j] = min { B[i,k] + di-1dkdj + B[k+1,j] } 501040140 d4d3d2d1d0 0 20,0000 9004000 290080016000 B[i, i] =0, i =1,..,4; B[1,2] = min {B[1,1] + B[2,2] + d0d1d2} = 1600 B[2,3] = min {B[2,2] + B[3,3]+ d1d2d3} = 400 B[3,4] = min {B[3,3] + B[4,4]+ d2d3d4} = 20,000 B[1,3]=min{B[1,1]+B[2,3]+d0d1d3, B[1,2]+B[3,3]+d1d2d3=min{800, 2000} = 8000 B[2,4]=min{B[2,2]+B[3,4]+d1d2d4, B[2,3]+B[4,4]+d1d3d4=min{22,000, 900} = 900 B[1,4] =min{B[1,1]+B[2,4]+d0d1d4, B[1,2]+B[3,4]+d0d2d4, B[1,3]+B[4,4]+d0d3d4} =min{2900, 41600,20400} = 2900 2013-09-22 Dao Thanh Tinh 29 Matrix Multiplication (8) 1. for i = 1 to n do B[[i,i] = 0; 2. for t = 1 to n-1 do for i =1 to n-t do B[i,i+t] = min{ B[i,k]+B[k+1,i+t] +di-1dkdi+t: i  k  i+t -1} DC[i,i+t] = chỉ số k mà tại đó tìm được B[i,i+t]; 3. output B[1,n]; Complexity: O(n3) 2013-09-22 Dao Thanh Tinh 30 Matrix Multiplication (9) void Viết biểu thức(i, j : Chỉ số); if (i=j) Viết( ‘A’, i) else k := DC[i, j]; Viết(‘(‘); Viết biểu thức(i, k); Viết(‘*’); Viết biểu thức(k+1,j ); Viết(‘)‘); 2013-09-22 Dao Thanh Tinh 31 Longest Monotonous Subsequence Problem: Cho dãy có n số S={X(1), X(2), ..., X(n)}. Hãy tìm dãy con đơn điệu không giảm dài nhất S* S S* = {X(p1), X(p2), ..., X(pk)}, nghĩa là X(p1)  X(p2)  ... X(pk), với p1 < p2 <...< pk, k max 2013-09-22 Dao Thanh Tinh 32 Longest Monotonous Subsequence (2) Algorithm: L[i] = số phần tử trong dãy con đơn điệu dài nhất của dãy Si = { X(1), X(2), ..., X(i) } có X(i) đứng sau cùng Ví dụ, dãy X có n=5: 12, 16, 5, 9, 6 L= 1, 2, 1, 2, 2 The length of longest monotonous subsequence k = max { L[1], ...., L[n] } 2013-09-22 Dao Thanh Tinh 33 Longest Monotonous Subsequence (3) Algorithm: Kí hiệu L[i] là số phần tử trong dãy con đơn điệu dài nhất của dãy Si = { X(1), X(2), ..., X(i) } có X(i) đứng sau cùng L[1] = 1 L[i] = max { L[j]: X(j)  X(i), j<i } + 1; nếu X(j)>X(i), 1j<i: đặt L[i] = 1; 2013-09-22 Dao Thanh Tinh 34 Longest Monotonous Subsequence (4) Algorithm: Đặt X(0) = ; L[0] = 0; Kí hiệu L[i] là số phần tử trong dãy con đơn điệu dài nhất của dãy Si = { X(0), X(1), X(2), ..., X(i) } có X(i) đứng sau cùng L[1] = 1 L[i] = max { L[j]: X(j)  X(i), 0  j<i } + 1; 2013-09-22 Dao Thanh Tinh 35 Longest Monotonous Subsequence (5) 8/47/35/23/1d/k 243122121L= 511746951612X= 987654321CS L[p] = max{L[i]: i=1,2,..,n} = 4, p =8  d4= 8 d3 = ? d3 = max { j<d4=8: L[j] = 3, X[j]  X[8] }  d3 = 7 d2 = ? d2 = max { j<d3=7: L[j] = 2, X[j]  X[7] }  d2 = 5 d1 = ? d1 = max { j<d2=5: L[j] = 2, X[j]  X[5] }  d1 = 3 2013-09-22 Dao Thanh Tinh 36 Longest Monotonous Subsequence (6) 8/47/35/23/1d/k 243122121L= 511746951612X= 987654321CS L[p] = max{L[i]: i=1,2,..,n} = 4, p =8  d4= 8 d3 = ? d3 = max { j<d4=8: L[j] = 3, X[j]  X[8] }  d3 = 7 d2 = ? d2 = max { j<d3=7: L[j] = 2, X[j]  X[7] }  d2 = 5 d1 = ? d1 = max { j<d2=5: L[j] = 2, X[j]  X[5] }  d1 = 3 Xác định dãy Ký hiệu L[p] = max { L[i]: i=1,2,...,n} dL[p] = p; for k= L[p] 1 downto 1 do dk =max {j: L[j]=k, j<dk+1, X(j)<X(dk+1)} output X(d1), X(d2), ..., X(dL[p]) 2013-09-22 Dao Thanh Tinh 37 Longest Common Subsequence Given a sequence X = {x1, x2, . . . , xn}. Sequence S = {s1, s2, . . . , sk} is a subsequence of X if there exists a strictly increasing sequence i1, i2, . . . , ik of indices of X such that for all j = 1, 2, . . . , k: xij = sj. For example, S = {B, C, D, B} is a subsequence of X = {A, B, C, B, D, A, B} with corresponding index sequence i = 2, 3, 5, 7 2013-09-22 Dao Thanh Tinh 38 Longest Common Subsequence (2) Example: X = { A, B, C, B, D, A, B } and Y = { B, D, C, A, B, A } S={ B, C, B, A } is common to both X and Y, has length 4. S={ B, C, B, A } is an LCS of X and Y Given two sequences X and Y, a sequence S is a common subsequence of X and Y if Z is a subsequence of both X and Y. 2013-09-22 Dao Thanh Tinh 39 Longest Common Subsequence (3) Problem: Given two sequences X = { x1, x2, . . . , xm } and Y = { y1, y2, . . . , yn } find a maximum-length common subsequence S of X and Y 2013-09-22 Dao Thanh Tinh 40 Longest Common Subsequence (4) Characteristics: Given two sequences X(m) = { x1,x2, ..., xm } and Y (n) = { y1,y2, ..., yn } S = S(k) = {s1,s2, ..., sk } be any LCS of X and Y. 1) sk= xm = yn  S (k-1) = {s1,s2, ...,sk-1} is LCS of X (m-1) and Y(n-1). 2) xm  yn, zk  xm  S is an LCS of X (m-1) and Y 3) xm  yn, zk  yn  S is an LCS of X and Y (n-1) 2013-09-22 Dao Thanh Tinh 41 Longest Common Subsequence (5) Remark: Given X(m) = { x1,x2, ..., xm } and Y (n) = { y1,y2, ..., yn } define S = S(k) = LCS { X(m), Y(n) } if xm = yn append xm to S (k-1) where S(k-1) is LCS of X(m-1) and Y(n-1). if xm  yn, S’ = LCS{ X (m-1), Y} S” = LCS{X, Y(n-1) } if |S’| > |S”| then S = S’ else S = S” 2013-09-22 Dao Thanh Tinh 42 Longest Common Subsequence (6) Computing the length of an LCS: Given X(m) = { x1,x2, ..., xm } and Y (n) = { y1,y2, ..., yn } define S = S(k) = LCS { X(m), Y(n) }, B[i,j] = lenght( LCS{X(i),Y(j)} ) formula: i>0, j>0: if xi = yj, B[i,j] = B[i-1, j-1] + 1 if xi  yj, B[i,j] = max { B[i-1, j], B[i,j-1] } i=0  j=0 B[i,j] = 0 2013-09-22 Dao Thanh Tinh 43 Longest Common Subsequence (7) Computing the length of an LCS: Given X(m) = { x1,x2, ..., xm } and Y (n) = { y1,y2, ..., yn } define S = S(k) = LCS { X(m), Y(n) }, B[i,j] = lenght( LCS{X(i),Y(j)} ) Algorithm: for (j=1; jn; j++) B[0,j] = 0; for (i=1; im; i++) B[i,0] = 0; for (i=1; im; i++) for (j=1; jn; j++) if (xi  yj) B[i,j] = max { B[i-1, j], B[i,j-1] } else B[i,j] = B[i-1,j-1] + 1; 2013-09-22 Dao Thanh Tinh 44 Longest Common Subsequence (8) Constructing an LCS: X = { A, B, C, B, D, A, B } and Y = { B, D, C, A, B, A } S = { B, C, B, A } 3 3 2 2 2 1 1 0 A 4 442210B7 432210A6 332210D5 332110B4 222110C3 221110B2 110000A1 000000xi0 ABCDByji 653210j= 2013-09-22 Dao Thanh Tinh 45 Longest Common Subsequence (9) 1. k = B[m,n]; i=m; j=n; 2. while (i>1)& (j>1) 1) if (X[i]=Y[j]) S[k]=X[i];i=i-1;j=j-1; else if(B[i,j-1]>B[i-1,j]) j=j-1; else i=i-1; 2) k = k – 1; 3 3 2 2 2 1 1 0 A 4 442210B7 432210A6 332210D5 332110B4 222110C3 221110B2 110000A1 000000xi0 ABCDByji 653210j= Complexity of Algorithm is O(mn) 2013-09-22 Dao Thanh Tinh 46 Knapsack Problem Cho túi có sức chứa W, W – số nguyên dương, tập S có n đồ vật trọng lượng: w1, w2, ..., wn giá trị v1, v2, ..., vn. Xếp như những đồ vật nào vào túi để tổng giá trị các đồ vật trong túi là lớn nhất? 2013-09-22 Dao Thanh Tinh 47 Knapsack Problem (2) (1) (2) (3) (4) (5) Plans: (2), (4) : 12kg, 9$ (2), (4) : 11kg, 15$ the optimal plan: (1), (3), (4), (5) 12 kg, 18$ 2013-09-22 Dao Thanh Tinh 48 Knapsack Problem (3) }1,0{:,...,2,1, max 1 1       i n i ii i n i i xniWxw xv 0-1 Knapsack Problem 2013-09-22 Dao Thanh Tinh 49 Knapsack Problem (4) }1,0{:,...,2,1, max 1 1       i n i ii i n i i xniWxw xv B[i,j] giá trị lớn nhất có được với túi có sức chứa j và xem xét các đồ vật 1, 2, ...,i i = 0, 1, ..., n j = 0, 1, ..., W Giá trị chứa trong túi bằng 0 khi: • Không sử dụng đồ vật nào, •hoặc sức chứa của túi bằng 0 j = 0,...,W B[0,j] = 0, i = 0,.., n B[i,0] = 0, 2013-09-22 Dao Thanh Tinh 50 Knapsack Problem (5) }1,0{:,...,2,1, max 1 1       i n i ii i n i i xniWxw xv B[i,j] giá trị lớn nhất có được với túi có sức chứa j và xem xét các đồ vật 1, 2, ...,i i = 0, 1, ..., n j = 0, 1, ..., W j = 0,...,W B[0,j] = 0, i = 0,.., n B[i,0] = 0, Tính B[i, j]: 1) Không thể sử dụng đồ vật i, do j<wi: B[i,j] = B[i-1,j] 2) Không sử dụng đồ vật i vì không lợi: B[i, j-wi] + vi < B[i-1,j] c) Sử dụng đồ vật i vì có lợi: B[i-1, j-wi] + vi ≥ B[i-1,j] B[n,T] – giá trị lớn nhất của đồ vật được xếp vào túi. 2013-09-22 Dao Thanh Tinh 51 Knapsack Problem (6) }1,0{:,...,2,1, max 1 1       i n i ii i n i i xniWxw xv B[i,j] giá trị lớn nhất có được với túi có sức chứa j và xem xét các đồ vật 1, 2, ...,i i = 0, 1, ..., n j = 0, 1, ..., W j = 0,...,W B[0,j] = 0, i = 0,.., n B[i,0] = 0, j<Wi: B[i,j] = B[i-1,j] j≥Wi: B[i,j] = max { B[i-1,j], B[i-1,j-wi]+vi} B[n,T] – giá trị lớn nhất của đồ vật được xếp vào túi. 2013-09-22 Dao Thanh Tinh 52 Knapsack Problem (7) B[i+1,j] = max { B[i,j], B[i,j-wi+1]+vi+1} B[0,j] = 0, j=0,...,W B[i,0] = 0, i=0,..n j = 0,...,w1-1 B[1,j] = 0, j = w1,...,W B[1,j] = v1 (1) (2) (3) (4) (5) 14 9 9 7 2 0 11 181414141412121042205 9988664442204 9977544442203 7775522222002 2222222222001 0000000000000 12109876543210j=i 2013-09-22 Dao Thanh Tinh 53 Knapsack Problem (8) for (i=0; i≤n;i++) B[i,0] = 0; for (j=0; j≤W;j++) B[0,j] = 0; for (i=1; i≤n;i++) for (j=1; j≤W;j++) if (wi<j) B[i,j] = B[i-1,j]; else B[i,j] = max { B[i-1,j], B[i-1, j-wi+1]+vi+1}; Complexity O(nW) The method described does not tell which subset gives the optimal solution. 2013-09-22 Dao Thanh Tinh 54 Knapsack Problem (9) Constructing the Optimal Solution 14 9 9 7 2 0 11 181414141412121042205 9988664442204 9977544442203 7775522222002 2222222222001 0000000000000 12109876543210j=i (1) (2) (3) (4) (5) used items: (1), (3), (4), (5) (2) (1) (3) (5) (4) 2013-09-22 Dao Thanh Tinh 55 Knapsack Problem (10) Constructing the Optimal Solution 14 9 9 7 2 0 11 181414141412121042205 9988664442204 9977544442203 7775522222002 2222222222001 0000000000000 12109876543210j=i remark: if B[i,j] > B[i-1,j]  item ith is used if B[i,j] = 0  in optimal solution: items 1, 2, ..,i are not used capacity amount j is not used 2013-09-22 Dao Thanh Tinh 56 Knapsack Problem (11) Constructing the Optimal Solution j = W; i = n; k = 0; while (B[i,j]>0) { while (B[i,j] = B[i  1,j]) i = i  1; k = k + 1; cs[k] = i; j = j  a[i]; i = i 1; } Output cs[k], cs[k-1], ..., cs[1] – chỉ số các đồ vật được dùng 2013-09-22 Dao Thanh Tinh 57 Knapsack Problem (12) }...,,1,0{:,...,2,1, max 1 1 ii n i ii i n i i cxniWxw xv     Bounded Knapsack Problem 2013-09-22 Dao Thanh Tinh 58 Knapsack Problem (13) }...,,1,0{:,...,2,1, max 1 1 ii n i ii i n i i cxniWxw xv     Bounded Knapsack Problem for (i=0; i≤n;i++) B[i,0] = 0; for (j=0; j≤W;j++) B[0,j] = 0; for (i=1; i≤n;i++) for (j=1; j≤W;j++) if (wi<j) B[i,j] = B[i-1,j]; else B[i,j] = max { B[i-1, j-kwi]+kvi, k= 0, 1, 2, ...,ci, j-kwi>0}; 2013-09-22 Dao Thanh Tinh 59 Knapsack Problem (14) ...},1,0{:,...,2,1, max 1 1     i n i ii i n i i xniWxw xv Unbounded Knapsack Problem 2013-09-22 Dao Thanh Tinh 60 Knapsack Problem (15) ...},1,0{:,...,2,1, max 1 1       i n i ii i n i i xniWxw xv Unbounded Knapsack Problem for (i=0; i≤n;i++) B[i,0] = 0; for (j=0; j≤W;j++) B[0,j] = 0; for (i=1; i≤n;i++) for (j=1; j≤W;j++) if (wi<j) B[i,j] = B[i-1,j]; else B[i,j] = max { B[i-1, j-kwi]+kvi, k= 0, 1, 2, ..., j-kwi>0}; 2013-09-22 Dao Thanh Tinh 61 Knapsack Problem (16) Ví dụ 4: Cho tập S có n đồ vật với giá