Bài giảng Phân tích và thiết kế thuật toán - Bài 9: Dynamic Programming (Part 1)

Nội dung text: Bài giảng Phân tích và thiết kế thuật toán - Bài 9: Dynamic Programming (Part 1)

1. 2/2/2017 Analysis and Design of Algorithms Lecture 9,10 Dynamic Programming Lecturer: Ha Dai Duong duonghd@mta.edu.vn 2/2/2017 1 Nội dung 1. Lược đồ chung 2. Bài toán tính số Fibonaci 3. Bài toán cái túi 4. Bài toán dãy con có tổng lớn nhất 5. Bài toán tìm xâu con chung dài nhất 6. Đường đi ngắn nhất - TT Floyd 7. Cây nhị phân tìm kiếm tối ưu 2/2/2017 2 Nội dung 1. Lược đồ chung 2. Bài toán tính số Fibonaci 3. Bài toán cái túi 4. Bài toán dãy con có tổng lớn nhất 5. Bài toán tìm xâu con chung dài nhất 6. Đường đi ngắn nhất - TT Floyd 7. Cây nhị phân tìm kiếm tối ưu 2/2/2017 3 1
2. 2/2/2017 Chia để trị • Khi chia bài toán thành các bài toán con, trong nhiều trường hợp, các bài toán con khác nhau lại chứa các bài toán con hoàn toàn giống nhau. • Ví dụ: Tính số Fibonaci thứ n, F(n): • F(0)=0, F(1)=1 • F(n)=F(n-2)+F(n-1) với n>1 • F(2)=1, F(3)= 2, F(4) = 3 , F(5)=5, F(6)=8 2/2/2017 4 Chia để trị • Fib(n): Tiếp cận theo hướng chia để trị F(n) = F(n-1) + F(n-2) Function Fib(n) { If n<2 then return n; else return Fib(n-1) + Fib(n-2); } 2/2/2017 5 Chia để trị • Fib(5) F5 F3 F4 F2 F3 F1 F2 F0 F1 F0 F1 F1 F2 F0 F1 Tính lại các bài toán con nhiều lần Khắc phục? Quy hoạch động 2/2/2017 6 2
3. 2/2/2017 Qui hoạch động • Là một kĩ thuật thiết kế thuật toán theo kiểu chia bài toán lớn thành các bài toán con, sử dụng lời giải của các bài toán con để tìm lời giải cho bài toán ban đầu. • Khác với chia để trị, quy hoạc động, thay vì gọi đệ quy, sẽ tính trước lời giải của các bài toán con và lưu vào bộ nhớ (thường là một mảng), và sau đó lấy lời giải của bài toán con ở trong mảng đã tính trước để giải bài toán lớn 2/2/2017 7 Qui hoặc động vs Chia để trị • Chia để trị: Tiếp cận từ trên xuống (Top- Down) F5 F3 F4 F2 F3 F1 F2 F0 F1 F0 F1 F1 F2 F0 F1 2/2/2017 8 Qui hoặc động vs Chia để trị • Chia để trị: Tiếp cận từ trên xuống (Top- Down) F5 F3 F4 F2 F3 F1 F2 F0 F1 F0 F1 F1 F2 F0 F1 2/2/2017 9 3
4. 2/2/2017 Qui hoặc động vs Chia để trị • Chia để trị: Tiếp cận từ trên xuống (Top- Down) F5 F3 F4 F2 F3 F1 F2 F0 F1 F0 F1 F1 F2 F0 F1 2/2/2017 10 Qui hoặc động vs Chia để trị • Chia để trị: Tiếp cận từ trên xuống (Top- Down) F5 F3 F4 F2 F3 F1 F2 F0 F1 F0 F1 F1 F2 F0 F1 2/2/2017 11 Qui hoặc động vs Chia để trị • Chia để trị: Tiếp cận từ trên xuống (Top- Down) F5 F3 F4 F2 F3 F1 F2 F0 F1 F0 F1 F1 F2 F0 F1 2/2/2017 12 4
5. 2/2/2017 Qui hoặc động vs Chia để trị • Chia để trị: Tiếp cận từ trên xuống (Top- Down) F5 F3 F4 F2 F3 F1 F2 F0 F1 F0 F1 F1 F2 F0 F1 2/2/2017 13 Qui hoặc động vs Chia để trị • Quy hoạch động: Tiếp cận từ dưới lên (Bottom-up) F5 F4 F3 F2 F1 F0 2/2/2017 14 Qui hoặc động vs Chia để trị • Quy hoạch động: Tiếp cận từ dưới lên (Bottom-up) F5 F4 F3 F2 F1 F0 2/2/2017 15 5
6. 2/2/2017 Qui hoặc động vs Chia để trị • Quy hoạch động: Tiếp cận từ dưới lên (Bottom-up) F5 F4 F3 F2 F1 F0 2/2/2017 16 Qui hoặc động vs Chia để trị • Quy hoạch động: Tiếp cận từ dưới lên (Bottom-up) F5 F4 F3 F2 F1 F0 2/2/2017 17 Qui hoặc động vs Chia để trị • Quy hoạch động: Tiếp cận từ dưới lên (Bottom-up) F5 F4 F3 F2 F1 F0 2/2/2017 18 6
7. 2/2/2017 Lược đồ chung • Phân rã: Chia bài toán cần giải thành những bài toán con nhỏ hơn đến mức có thể giải trực tiếp được hay không?? -> Nếu được • Giải các bài toán con và ghi nhận lời giải: Lưu trữ lời giải của các bài toán con vào một bảng để sử dụng về sau. • Tổng hợp lời giải: – Tổng hợp lời giải các bài toán con kích thước nhỏ hơn thành lời giải bài toán lớn hơn. – Tiếp tục cho đến khi thu được lời giải của bài toán xuất phát (là bài toán con có kích thước lớn nhất) 2/2/2017 19 Nội dung 1. Lược đồ chung 2. Bài toán tính số Fibonaci 3. Bài toán cái túi 4. Bài toán dãy con có tổng lớn nhất 5. Bài toán tìm xâu con chung dài nhất 6. Đường đi ngắn nhất - TT Floyd 7. Cây nhị phân tìm kiếm tối ưu 2/2/2017 20 Tính số Fibonaci bằng QHD • Phân rã: F(n) = F(n-1) + F(n-2) • Giải bài toán con F(0) = 0 F(1) = 1 • Tổng hợp F(n) = F(n-1) + F(n-2) 2/2/2017 21 7
8. 2/2/2017 Cài đặt Function DPFib(n) { F[0] = 0; F[1] = 1; If (n>1) { For k = 2 to n { F[k] = F[k-1] + F[k-2];} } return F[n]; } 2/2/2017 22 Minh họa • Tính DPFib(5) = 5 Function DPFib(n) { F[0] = 0; F[1]=1; k=2: F(2)=F(1)+F(0)=1+0=1 If (n>1) { K=3: F(3)=F(2)+F(1)=1+1=2 For k = 2 to n { F[k] = F[k-1] + F[k-2]; K=4: F(4)=F(3)+F(2)=2+1=3 } } K=5: F(5)=F(4)+F(3)=3+2=5 return F[n]; 2/2/2017} 23 Cài đặt khác Function DPFib2(n) { Fk2 = 0; Fk1 = 1; k=2 While (k<=n) { tg = Fk1; Fk1 = Fk1 + Fk2; Fk2 = tg; k = k+1; } return Fk1; } 2/2/2017 24 8
9. 2/2/2017 Đánh giá • Thuật toán 1 DPFib(n) – Bộ nhớ ?? – Thời gian ?? • Thuật toán 2 DPFib2(n) – Bộ nhớ ?? – Thời gian ?? 2/2/2017 25 Nội dung 1. Lược đồ chung 2. Bài toán tính số Fibonaci 3. Bài toán cái túi 4. Bài toán dãy con có tổng lớn nhất 5. Bài toán tìm xâu con chung dài nhất 6. Đường đi ngắn nhất - TT Floyd 7. Cây nhị phân tìm kiếm tối ưu 2/2/2017 26 Bài toán (Knapsack Problem) • Có n đồ vật, đồ vật i có trọng lượng wi và giá trị ci, i = 1, 2, , n. • Tìm cách chất các đồ vật này vào cái túi có dung lượng là b sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất. 2/2/2017 27 9
10. 2/2/2017 Bài toán (Knapsack Problem) • Có n đồ vật, đồ vật i có trọng lượng wi và giá trị ci, i = 1, 2, , n. • Tìm cách chất các đồ vật này vào cái túi có dung lượng là b Kết quả nhận PP Tham lam được thường là không tối ưu 2/2/2017 28 Giải bằng QHD ??? • Có: n - Số đồ vật, b - trọng lượng túi (nguyên) • Phân rã: Với các giá trị i (1 n) và L (0 b) Gọi MaxV(i,L) là tổng giá trị lớn nhất có thể chọn trong i đồ vật (từ 1 đến i) với trọng lượng tối đa của túi là L. Khi đó MaxV(n,b) là giá trị lớn nhất mang đi được. • Giải bài toán con: MaxV(0,L) = 0 với L, và MaxV(i,0) = 0 với i. 2/2/2017 29 Giải bằng QHD ??? • Tổng hợp: – Đã có MaxV(i-1,L): Giá trị lớn nhất mang đi được với i-1 đồ vật khi trọng lượng túi là L. – Xét đồ vật thứ i khi trọng lượng túi vẫn là L: • Chỉ mang thêm đồ vật thứ i khi giá trị của túi lúc mang i-1 đồ vật ở trọng lượng túi là L-w[i] (như thế mới đảm bảo mang thêm được đồ vật i có trọng lượng w[i] khi trọng lượng túi là L) cộng với giá trị của đồ vật thứ i, c[i], lớn hơn khi không mang đồ vật thứ i, MaxV(i-1,L). • Nghĩa là MaxV(i, L) = Max{MaxV(i-1,L-w[i])+c[i], MaxV(i-1,L)} 2/2/2017 30 10
11. 2/2/2017 Cài đặt Procedure Bag_best { For L= 0 to b do MaxV[0,L] =0 ; For i= 0 to n do MaxV[i,0] =0 ; For i = 1 to n do For L = 1 to b do MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i] ; return MaxV(n, b) ; } 2/2/2017 31 Minh họa • Cho 6 đồ vật (n = 6), và túi có trọng lượng b = 19. Các đồ vật có trọng lượng và giá trị như sau: i c w 1 7 3 2 10 4 3 20 5 4 19 7 5 13 6 6 40 9 2/2/2017 32 Khởi tạo • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 10 4 2 0 20 5 3 0 19 7 4 0 13 6 5 0 40 9 6 0 2/2/2017 33 11
12. 2/2/2017 Lặp • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 10 4 2 0 20 5 3 0 19 7 4 0 13 6 5 0 40 9 6 0 MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i]; 2/2/2017 34 Lặp • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 10 4 2 0 20 5 3 0 19 7 4 0 13 6 5 0 40 9 6 0 MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i]; 2/2/2017 35 Lặp • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 0 10 4 2 0 20 5 3 0 19 7 4 0 13 6 5 0 40 9 6 0 MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i]; 2/2/2017 36 12
13. 2/2/2017 Lặp • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 0 7 10 4 2 0 20 5 3 0 19 7 4 0 13 6 5 0 40 9 6 0 MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i]; 2/2/2017 37 Lặp • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 0 7 7 10 4 2 0 20 5 3 0 19 7 4 0 13 6 5 0 40 9 6 0 MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i]; 2/2/2017 38 Lặp • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 10 4 2 0 20 5 3 0 19 7 4 0 13 6 5 0 40 9 6 0 MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i]; 2/2/2017 39 13
14. 2/2/2017 Lặp • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 10 4 2 0 0 0 7 20 5 3 0 19 7 4 0 13 6 5 0 40 9 6 0 MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i]; 2/2/2017 40 Lặp • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 10 4 2 0 0 0 7 10 20 5 3 0 19 7 4 0 13 6 5 0 40 9 6 0 MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i]; 2/2/2017 41 Lặp • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 10 4 2 0 0 0 7 10 10 20 5 3 0 19 7 4 0 13 6 5 0 40 9 6 0 MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i]; 2/2/2017 42 14
15. 2/2/2017 Lặp • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 10 4 2 0 0 0 7 10 10 10 20 5 3 0 19 7 4 0 13 6 5 0 40 9 6 0 MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i]; 2/2/2017 43 Lặp • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 10 4 2 0 0 0 7 10 10 10 ? 20 5 3 0 19 7 4 0 13 6 5 0 40 9 6 0 MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i]; 2/2/2017 44 Lặp • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 10 4 2 0 0 0 7 10 10 10 17 20 5 3 0 19 7 4 0 13 6 5 0 40 9 6 0 MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i]; 2/2/2017 45 15
16. 2/2/2017 Lặp • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 10 4 2 0 0 0 7 10 10 10 17 17 17 17 17 17 17 17 17 17 17 17 17 20 5 3 0 19 7 4 0 13 6 5 0 40 9 6 0 MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i]; 2/2/2017 46 Lặp • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 10 4 2 0 0 0 7 10 10 10 17 17 17 17 17 17 17 17 17 17 17 17 17 20 5 3 0 0 0 7 10 20 20 20 27 30 30 30 37 37 37 37 37 37 37 37 19 7 4 0 0 0 7 10 20 20 20 27 30 30 30 39 39 39 46 49 49 49 56 13 6 5 0 0 0 7 10 20 20 20 27 30 30 33 39 39 40 46 49 49 52 56 40 9 6 0 0 0 7 10 20 20 20 27 40 40 40 40 50 60 60 60 67 70 70 MaxV[i,L] = MaxV[ i-1,L]; If [(L w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])] MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i]; 2/2/2017 47 Kết thúc • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 10 4 2 0 0 0 7 10 10 10 17 17 17 17 17 17 17 17 17 17 17 17 17 20 5 3 0 0 0 7 10 20 20 20 27 30 30 30 37 37 37 37 37 37 37 37 19 7 4 0 0 0 7 10 20 20 20 27 30 30 30 39 39 39 46 49 49 49 56 13 6 5 0 0 0 7 10 20 20 20 27 30 30 33 39 39 40 46 49 49 52 56 40 9 6 0 0 0 7 10 20 20 20 27 40 40 40 40 50 60 60 60 67 70 70 Những vật được mang đi: Tổng trọng lượng vật: Tổng giá trị: 2/2/2017 48 16
17. 2/2/2017 Kết thúc • n = 6, b = 19 i/L 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 1 0 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 10 4 2 0 0 0 7 10 10 10 17 17 17 17 17 17 17 17 17 17 17 17 17 20 5 3 0 0 0 7 10 20 20 20 27 30 30 30 37 37 37 37 37 37 37 37 19 7 4 0 0 0 7 10 20 20 20 27 30 30 30 39 39 39 46 49 49 49 56 13 6 5 0 0 0 7 10 20 20 20 27 30 30 33 39 39 40 46 49 49 52 56 40 9 6 0 0 0 7 10 20 20 20 27 40 40 40 40 50 60 60 60 67 70 70 Những vật được mang đi: {2, 3, 6} Tổng trọng lượng vật: 18 Tổng giá trị: 70 2/2/2017 49 Nội dung 1. Lược đồ chung 2. Bài toán tính số Fibonaci 3. Bài toán cái túi 4. Bài toán dãy con có tổng lớn nhất 5. Bài toán tìm xâu con chung dài nhất 6. Đường đi ngắn nhất - TT Floyd 7. Cây nhị phân tìm kiếm tối ưu 2/2/2017 50 Bài toán • Cho mảng N số: A[1 N ] • Hãy tìm dãy con các phần tử liên tiếp của A có tổng lớn nhất. • Ví dụ: 13, -15, 2, 18, 4, 8, 0, -5, -8 Thì dãy con cần tìm là A(3)-A(6) 13, -15, 2, 18, 4, 8, 0, -5, -8 (Đã giải quyết theo phương pháp chia để trị) 2/2/2017 51 17
18. 2/2/2017 Tiếp cận qui hoặc động • Phân rã: – Gọi MaxS[i] là tổng lớn nhất của dãy con liên tiếp có i phần tử a[1] a[i]. – Khi đó MaxS[N] là giá trị lớn nhất của dã con liên tiếp cần tìm • Bài toán cơ sở: – Với i = 1 ta có MaxS[i] = a[i] 2/2/2017 52 Tổng hợp • Giả sử i > 1 và MaxS[k] là đã biết với k = 1, , i-1. Ta cần tính MaxS[i] là tổng của dãy con liên tiếp lớn nhất của dãy a[1] , a[i-1], a[i]. • Các dãy con liên tiếp của dãy này có thể là một trong hai trường hợp: . Các dãy con liên tiếp có chứa a[i] . Các dãy con liên tiếp không chứa a[i] 2/2/2017 53 Tổng hợp • Gọi MaxE[i] là tổng lớn nhất của các dãy con liên tiếp của dãy a[1] a[i] chứa chính a[i]. • Tổng lớn nhất của các dãy con liên tiếp của dãy a[1] a[i] không chứa a[i] chính là tổng lớn nhất của các dãy con của dãy a[1] a[i-1], nghĩa là MaxS[i-1]. MaxS[i] = max{MaxS[i-1], MaxE[i]} 2/2/2017 54 18
19. 2/2/2017 Tính MaxE[i] • Để tính MaxE[i], i = 1, 2, , n, ta cũng có thể sử dụng công thức đệ quy như sau: – Với i=1 thì MaxE[i] = a[1]; – Với i >1, Gọi C là dãy con kế tiếp lớn nhất của dãy a[1] a[i] có chứa a[i]. Có hai khả năng: • Nếu C chứa a[i-1] thì tổng lớn nhất là MaxE[i-1]+a[i]; • Nếu C không chứa a[i-1] thì C chỉ gồm a[i] và tổng lớn nhất là a[i] MaxE[i] = max {a[i], MaxE[i-1]+a[i]}, i>1 2/2/2017 55 Cài đặt Procedu subMax • s - chỉ số đầu { • e - chỉ số cuối MaxS=a[1]; MaxE= a[1]; s=1; e=1; s1=1; • s1 - chỉ số đầu tạm For i = 2 to n do { if MaxE>0 then MaxE=MaxE+a[i] else {MaxE = a[i]; s1=i; } if (MaxE > MaxS) then { MaxS = MaxE; e=i; s=s1; } } } 2/2/2017 56 Minh họa • Dãy a[1 9] = 13, -15, 2, 18, 4, 8, 0, -5, -8 2/2/2017 57 19
20. 2/2/2017 Bài tập 1. Thực hiện từng bước bài toán cái túi với dữ liệu: – Trọng lượng túi b=10 – Số lượng đồ vật n=6 – Các vật w{6 ,3 ,3 ,7 ,4 ,3} giá trị v{12,1,8 ,1 ,10 ,3} 2. Cho dãy A={-98,54,67, 65,-879,78,65,21,- 6,67}, tìm dãy con dài nhất theo phương pháp qui hoạch động. 2/2/2017 58 Bài tập 3. Cài đặt thuật toán giải bài toán cái túi theo phương pháp qui hoạch động. Đánh giá độ phức tạp bằng thực nghiệm và so sánh với lý thuyết. 4. Cài đặt thuật toán tìm dãy con lớn nhất theo phương pháp qui hoạch động. Đánh giá độ phức tạp bằng thực nghiệm và so sánh với lý thuyết. 2/2/2017 59 20