Bài giảng Cấu trúc dữ liệu và thuật giải - Bài 6: Một số vấn đề cơ sở của Tin học

Nội dung text: Bài giảng Cấu trúc dữ liệu và thuật giải - Bài 6: Một số vấn đề cơ sở của Tin học

1. Tổng quan về phương pháp Quy hoạch động • Quy hoạch động thường dùng giải các bài toán tối ưu có bản chất đệ qui • Việc tìm nghiệm tối ưu của bài toán đã cho được thực hiện dựa trên việc tìm nghiệm tối ưu của các bài toán con. • Kết quả của các bài toán con được ghi nhận lại để phục vụ cho việc giải các bài toán lớn hơn và giải được bài toán yêu cầu. 3 Ví dụ minh họa: Dãy Fibonnaci là dãy các số nguyên dương được định nghĩa như sau: 1i 2 F i][ F[ i 2] F [ i 1] i 2 int F(int i) int F[100]; //Bang phuong an { void main() if (i <= 2) return 1; { return F(i-2) + F(i-1); F[1] = F[2] = 1; } for(int i = 3; i <= 6; i++) void main() F[i] = F[i-2] + F[i-1]; { cout << F[6]<<endl; cout<<F(6)<<endl; } } 4 2
2. Bài toán ba lô (knapsack) Cho n gói hàng. Gói hàng thứ i có khối lượng là A[i] và giá trị C[i]. Cần chọn những gói hàng nào để bỏ vào một ba lô sao tổng giá trị của các gói hàng đã chọn là lớn nhất nhưng tổng khối lượng của chúng không vượt quá khối lượng M cho trước. Mỗi gói chỉ chọn 1 hoặc không chọn. Ví dụ: n = 5; M = 13 i 1 2 3 4 5 A[i] 3 4 5 2 1 C[i] 4 5 6 3 1 Tổng giá trị của các gói hàng bỏ vào ba lô: 16 Các gói được chọn: 1(3, 4) 2(4, 5) 3(5, 6) 5(1, 1) 7 Tham số thể hiện kích thước bài toán • Kết quả bài toán là tổng giá trị lớn nhất của các món hàng được chọn trong n món sao cho tổng khối lượng không lớn hơn M cho trước, ký hiệu là F(n) • Tham số thể hiện kích thước bài toán là số món hàng n • Giá trị của F(n) có thể được tính từ giá trị của F(n-1) cộng thêm hoặc không cộng thêm giá trị của món hàng thứ n nhưng tổng khối lượng không lớn hơn M. • Nếu chọn thêm món hàng thứ n thì tổng khối lượng được chọn trong (n-1) món hàng không lớn hơn (M-A[n]) • Suy ra bài toán có 2 tham số: số món hàng và khối lượng giới hạn 8 4
3. Ví dụ bảng phương án: • Trường hợp A[i] > v: F(i, v) = F(i -1, v) • Trường hợp A[i] <= v: F(i, v) = Max{ F(i -1, v); F(i -1, v – A[i]) + C[i]) } C A v0 1 2 3 4 5 6 7 8 9 10 11 12 13 i 00 0 0 0 0 0 0 0 0 0 0 0 0 0 4 3 10 0 0 4 4 4 4 4 4 4 4 4 4 4 5 4 20 0 0 4 5 5 5 9 9 9 9 9 9 9 6 5 30 0 0 4 5 6 6 9 10 11 11 11 15 15 3 2 40 0 3 4 5 7 8 9 10 12 13 14 15 15 1 1 50 1 3 4 5 7 8 9 10 12 13 14 15 16 11 Thuật toán tạo bảng phương án void TaoBangPhuongAn(F[0 n][0 M]) { for (v=0; v <= M; v++) F[0, v] = 0; // Điền số 0 cho dòng 0 của bảng for (i = 1; i <= n; i++) for (v=0; v <= M; v++) { F[i, v] = F[i-1, v]; If (A[i] <= v && F[i, v] < F[i-1, v - A[i] ] + C[i]) F[i, v] = F[ i-1, v - A[i] ] + C[i]; } } 12 6
4. Bài toán ba lô 2 Cho n loại hàng. Món hàng thuộc loại hàng i có khối lượng A[i] và giá trị C[i]. Số lượng các món hàng của mỗi loại không hạn chế. Cần chọn các món hàng trong từng loại để bỏ vào một ba lô sao cho tổng giá trị của các món hàng đã chọn là lớn nhất nhưng tổng khối lượng của chúng không vượt quá khối lượng M cho trước. Cho biết số lượng món hàng từng loại hàng được chọn Ví dụ: n = 5; M = 13 i 1 2 3 4 5 A[i] 3 4 5 2 1 C[i] 4 5 6 3 1 Tổng giá trị của các món hàng bỏ vào ba lô: 19 Các món được chọn: 1 gói hàng loại 1 có khối lượng 3 và giá trị 4 5 gói hàng loại 4 có khối lượng 2 và giá trị 3 15 Xác định công thức đệ quy Gọi F(i, v) là tổng giá trị lớn nhất của các món hàng được chọn sao cho tổng khối lượng v: F(i, v) = F(i-1, v) • Trường hợp A[i] <= v: – Nếu loại hàng i không được chọn thì: F(i, v) = F(i-1, v) – Nếu có k món hàng loại i được chọn: (1 <= k <= v/A[i] ) F(i, v) = F(i-1, v – A[i]*k) + C[i]*k Do đó: F(i, v) = Max{F(i-1, v – A[i]*k) + C[i]*k } k [0, v/A[i]] • Bài toán nhỏ nhất ứng với i = 0 hay v=0 ta có: F(0, v) = 0 16 8
5. Ví dụ: Lập bảng phương án F • Với i > 0 : – A[i] > v : F(i, v) = F(i - 1, v) – A[i] <= v : F(i, v) = Max{ F(i-1, v – A[i]*k) + C[i]*k } với k [0, v/A[i] ] Bảng F[i, v] C[i] A[i] v 0 1 2 3 4 5 6 7 8 9 10 11 12 13 i 0 0 0000000000000 4 3 1 0 0 0 4 4 4 8 8 8 12 12 12 16 16 5 4 2 0 0 0 4 4 5 8 9 9 12 13 14 16 17 6 5 3 0 0 0 4 4 5 8 9 10 12 13 14 16 17 3 2 4 0 0 0 4 4 7 8 10 11 13 14 16 17 19 1 1 5 0 0 1 4 5 7 8 10 11 13 14 16 17 19 19 Ví dụ lập bảng phương án S C[i] A[i] v 0 1 2 3 4 5 6 7 8 9 10 11 12 13 i 0 0 0000000000000 Bảng 4 3 1 0 0 0 4 4 4 8 8 8 12 12 12 16 16 5 4 F[i, v] 2 0 0 0 4 4 5 8 9 9 12 13 14 16 17 6 5 3 0 0 0 4 4 5 8 9 10 12 13 14 16 17 3 2 4 0 0 0 4 4 7 8 10 11 13 14 16 17 19 1 1 5 0 0 1 4 5 7 8 10 11 13 14 16 17 19 C[i] A[i] v 1 2 3 4 5 6 7 8 9 10 11 12 13 i 4 3 1 0011122233344 Bảng 5 4 2 0000101101201 S[i, v] 6 5 3 0000000100000 3 2 4 0000102132435 1 1 5 0101000000000 20 10
6. Thuật toán truy vết tìm lại các gói hàng đã chọn void TruyVet(S[1 n][1 M]) { i = n; v = M while (i > 0) { if (S[i, v] != 0) { ; v = v – S[i, v]*A[i]; } i = i – 1; } } 23 Bài toán dãy con có tổng chia hết cho k Cho một dãy A gồm n số nguyên và một số nguyên dương k. Hãy tìm một dãy con (không nhất thiết phải liên tiếp nhau) dài nhất có tổng các số chia hết cho số k. Ví dụ: n = 6 và k = 5 I 1 2 3 4 5 6 Dãy A[i] 11 6 7 12 20 8 Chiều dài dãy con: 4 Các phần tử được chọn là : 1 2 5 6 Có giá trị tương ứng là : : 11 6 20 8 24 12
7. Lập công thức đệ qui Gọi F(i, v) = chiều dài dãy con dài nhất trong miền [1 i] có tổng chia với k dư là v. 1. Nếu dãy con dài nhất không có A[i] thì F(i, v) = F(i-1, v) 2. Nếu dãy con dài nhất có chứa A[i]: Gọi r = A[i] mod k ta có F(i, v) = F(i-1, v - r) + 1 – Nếu v – r = 0 : F(i, v) = F(i-1, 0) + 1 – Nếu v – r > 0 và F(i-1, v - r)>0: F(i, v) = F( i-1, v - r) + 1 – Nếu v – r 0: F(i, v) = F( i-1, v-r+k) + 1 thay (v - r) mod k = (v – r + k) mod k • Bài toán nhỏ nhất ứng với i = 1: • F(1,v)= 0 nếu r v – F(1, v) = 1 nếu r = v • Với i > 1 : – Nếu v = r thì : F(i, v) = Max {F(i-1, v), F(i-1, 0) +1 } – Nếu v > r và F(i-1, v- r) >0 thì F(i, v) = Max {F(i-1, v), F(i-1, v – r) +1 } – Nếu v 0 thì F(i, v) = Max{F(i-1, v), F(i-1, v – r + k) + 1} 28 14
8. Ví dụ bảng phương án: • Với i > 1 : – Nếu v = r thì : F(i, v) = Max {F(i-1, v), F(i-1, 0) +1 } – Nếu v 0 thì F(i, v) = Max {F(i-1, v), F(i-1, (v – r + k) mod k) +1 } i r=A[i] v 0 1 2 3 4 1 1 0 1 0 0 0 2 1 4 | 0 0 | 1 1 | 2 2 | 0 3 | 0 3 2 3 | 0 4 | 1 0 | 2 1 | 2 2 | 3 4 2 3 | 3 4 | 3 0 | 2 1 | 2 2 | 3 5 0 0 | 4 1 | 4 2 | 3 3 | 3 4 | 4 6 3 2 | 4 3 | 4 4 | 5 1 | 5 2 | 6 31 Thuật toán tạo bảng phương án void TaoBangPhuongAn(F[1 n][0 k-1]) { for (v=0; v 0 && F[i, v] <= F[i-1, (v - r + k)%k]) F[i, v] = F[ i -1, (v - r + k)%k] + 1; } } 32 16
9. Xác định tham số thể hiện kích thước bài toán • Gọi L(n) là độ dài dãy con không giảm dài nhất trong miền [1 n] – L(n) = L(n-1) nếu dãy con dài nhất trong miền [1 n-1] không có A[n] – L(n) = L(n-1) +1 nếu dãy con dài nhất trong miền [1 n-1] có A[n] • Do đó tham số thể hiện kích thước bài toán là số phần tử n. • Xét 2 cách ghi nhận kết quả các bài toán con: I 1 2 3 4 5 6 7 8 9 10 Dãy A 2 6 -7 5 8 1 -3 5 15 4 Cách 1 1 2 2 2 3 3 3 3 4 4 Cách 2 1 2 1 2 3 2 2 3 4 3 35 Lập công thức đệ qui Gọi L(i) là độ dài dãy con dài nhất trong dãy A[1 i] và có A[i] là phần tử cuối dãy con dài nhất đó. • Nếu A[i] < A[j] với mọi j < i thì: L(i) = 1 • Ngược lại thì : L(i) = Max{ L(j) : j < i và A[j] <= A[i] } + 1 • Bài toán nhỏ nhất với đoạn A[1 1] thì L(1) = 1 I 1 2 3 4 5 6 7 8 9 10 Dãy A[i] 2 6 -7 5 8 1 -3 5 15 4 L(i) 1 2 1 2 3 2 2 3 4 3 36 18
10. Truy vết tìm lại các phần tử trên dãy con • Bắt đầu từ phần tử i có giá trị L[i] có lớn nhất là phần tử cuối cùng trong dãy con dài nhất. • Truy tiếp sang phần tử có chỉ số Trươc[i] cho đến khi phần tử Truoc[i] = 0. I 1 2 3 4 5 6 7 8 9 10 Dãy A[i] 2 6 -7 5 8 1 -3 5 15 4 L[i] 1 2 1 2 3 2 2 3 4 3 Truoc[i] 0 1 0 3 4 3 3 7 8 7 39 Thuật toán truy vết tìm lại các phần tử trên dãy con tối ưu void TruyVet() I 1 2 3 4 5 6 7 8 9 10 A[i] 2 6 -7 5 8 1 -3 5 15 4 { B[i] 1 2 1 2 3 2 2 3 4 3 i = n; Truoc[i] 0 1 0 3 4 3 3 7 8 7 for ( j = n-1; j >=1; j ) if (B[j] > B[i]) i = j; while ( i > 0) { ; i = Truoc[i]; } ; } 40 20
11. Lập công thức đệ qui • Scn[i] lưu số công nhân cần thuê cho tháng thứ i • Smax là số công nhân của tháng cần nhiều người nhất • Bài toán con nhỏ nhất ứng với i = 1 (tháng đầu tiên): C(1, j) = j * (DV + LT) với j = Scn[1] Smax • C(i, j) là chi phí tối thiểu của i tháng đầu tiên nếu tại tháng thứ i có j công nhân được thuê. C(i, j) = Min{ C(i-1, k) + chi phí để từ k người thành j người } ( i=2 T; j =Scn[i] Smax; k = Scn[i-1] Smax) • Kết quả bài toán là: Kq = Min{C(T, j) + chi phí sa thải j người} j=Scn[T] Smax 43 Xây dựng bảng chứa C(i, j) • Mảng C[1 T+1, 1 Smax]: C[i, j] ghi nhận giá trị C(i, j) C(1, j) = j * (DV + LT) với j = Scn[1] Smax C(i, j) = Min{ C(i-1, k) + chi phí để từ k người thành j người } ( i=1 T; j =Scn[i] Smax; k = Scn[i-1] Smax) C(T+1, j) = C(T, j) + (j * ST) j=Scn[T] Smax Scn i \ j 9 10 11 11 1 99 9 2 99+45+12=156 99+50+6=155 99+55=164 10 3 155+50=205 155+55+4=214 4 205+60=265 2144+66=280 44 22
12. Thuật toán truy vết số công nhân mỗi tháng { //Tìm số nhân công của tháng thứ T S = C[T+1, Scn[T] ]; k = Scn[T]; for (j=Scn[T]+1; j C[T+1, j ]) { k = j; S =C[T+1, j ]; } for (i=T; i > 1; i ) { k = Truoc[i, k]; } } 47 Bài tập 1. Có N gói kẹo, gói thứ i có Ai cái kẹo. Không được bóc bất kỳ một gói kẹo nào, cần chia N gói kẹo thành hai phần sao cho độ chênh lệch số kẹo giữa hai gói là ít nhất. 2. Cho n loại tờ giấy bạc. Tờ giấy bạc thứ i có mệnh giá A[i]. Số tờ mỗi loại không giới hạn. Cần chi trả cho khách hàng số tiền M đồng. Hãy cho biết mỗi loại tiền cần bao nhiêu tờ sao cho tổng số tờ là ít nhất. Nếu không đổi được, thì thông báo “KHONG DOI DUOC”. 3. Cho n loại tờ giấy bạc. Tờ giấy bạc thứ i có mệnh giá A[i]. Giả thiết loại tiền mệnh giá A[i] có B[i] tờ (i := 1, n). Cần chi trả cho khách hàng số tiền M đồng. Hãy cho biết mỗi loại tiền cần bao nhiêu tờ sao cho tổng số tờ là ít nhất. Nếu không đổi được, thì thông báo “KHONG DOI DUOC”. 4. Cần cắm k loại hoa khác nhau vào n lọ xếp thẳng hàng sao cho loại hoa có số hiệu nhỏ được đặt trước hoa có số hiệu lớn. Với mỗi loại hoa i ta biết giá trị thẩm mỹ khi cắm hoa đó vào lọ j là v[i,j]. Hãy tìm phương án cấm các loại hoa trên vào n lọ sao cho tổng giá trị thẩm mỹ là lớn nhất. 5. Một hộp thư điện tử cho phép gửi đính kèm một hoặc nhiều file vào một thư điện tử sao cho tổng dung lượng các file đính kèm trên thư điện tử không vượt quá kích thước M KByte cho trước. Để có số thư điện tử gửi đi là ít nhất, người ta cần chọn trong N file dữ liệu các file để đính kèm vào một email sao cho tổng dung lượng của các file đính kèm là lớn nhất nhưng không vượt quá kích thước M. Giả sử, M 100; N 50 và file thứ i trong N file dữ liệu có kích thước là Ai KByte (là số nguyên dương). Hãy trình bày thuật toán để chọn trong N file dữ liệu các file đính kèm vào một thư điện tử theo yêu cầu trên, liệt kê kích thước các file đã chọn. 48 24