ươ
Ch
ộ
ạ
ươ
ng 4 ng pháp quy ho ch đ ng
Ph
minhthai@huflit.edu.vn www.minhthai.edu.vn
Ầ Ạ
TR N MINH THÁI – Ứ PH M Đ C THÀNH –
phamducthanh@huflit.edu.vn www.phamthao.com
1 9/17/16 Trần Minh Thái - Phạm Đức Thành
Nội dung
v 4.1. Ý tưởng và nguyên lý v 4.2. Công thức truy hồi v 4.3. Một số bài toán quy hoạch động v 4.4. Tóm tắt chương v 4.5. Bài tập
2 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.1] Ý tưởng và nguyên lý
v Một ví dụ giới thiệu về bài toán quy hoạch:
y
R= 1
x
O
mặt “Trong phẳng xOy, tìm điểm có tọa độ (x, y) sao cho x2+y2<=1 và x+y có giá trị tốt nhất”
3 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.1] Ý tưởng và nguyên lý
v Những điểm (x, y) thỏa điều kiện x2+y2<=1 là những điểm có tọa độ nằm trong hình tròn có tâm O (gốc tọa độ) và bán kính R=1.
v Vì thế, nghiệm cần tìm phải nằm trong hình
tròn (O, 1).
4 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.1] Ý tưởng và nguyên lý
5 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.1] Ý tưởng và nguyên lý
y
phân giác thứ nhất
R=1
tiếp tuyến x
O
6 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.1] Ý tưởng và nguyên lý
Bài toán trên gọi là tối ưu (bài toán quy hoạch). Trong đó: v Có một hàm ƒ gọi là hàm mục tiêu (hay đánh giá). v Một số hàm cho giá trị luận lý ǥ1, ǥ2, .., ǥn (hàm
ràng buộc).
v Một nghiệm x là tốt nhất khi:
x thỏa điều kiện ràng buộc ǥi (x) = true, với mọi i: 1<=i<=n.
v Không tồn tại một x’ nào thỏa ràng buộc mà ƒ(x’)
7
tốt hơn ƒ(x). 9/17/16
Trần Minh Thái - Phạm Đức Thành
[4.1] Ý tưởng và nguyên lý
v Với bài vừa xét ở trên, ta có: v Hàm ƒ: ƒ(x,y) = x+y. v Hàm ràng buộc ǥ: x2+y2<=1. v Một nghiệm x là tốt nhất với ý nghĩa là lớn nhất. v Các bài toán quy hoạch rất phong phú, đa dạng và nhiều ứng dụng thực tế. Tuy nhiên có một số bài toán chưa giải được.
8 9/17/16 Trần Minh Thái - Phạm Đức Thành
Phương pháp quy hoạch động
v Richard Bellman phát minh - 1953. v Ý tưởng của nguyên lý tối ưu Bellman là
Ø “Với mỗi quá trình điều khiển tối ưu, đối với trạng thái bắt đầu A0, với trạng thái A trong quá trình đó, phần quá trình kể từ trạng thái A xem như trạng thái bắt đầu cũng là tối ưu”.
Ø “Nếu một cấu hình là tối ưu thì mọi cấu
hình con của nó cũng là tối ưu”.
9 9/17/16 Trần Minh Thái - Phạm Đức Thành
Phương pháp quy hoạch động v Dùng để giải các bài toán tối ưu có bản chất là
đệ quy: Ø Việc tìm phương án tối ưu có thể đưa về
tìm tối ưu cho các bài toán con hữu hạn.
Ø Thuật toán đệ quy đã tìm hiểu ở chương 3 đa số là dùng nguyên lý “chia để trị” và trong quy hoạch động cũng áp dụng nguyên lý này.
10 9/17/16 Trần Minh Thái - Phạm Đức Thành
Hai loại quy hoạch động
v Phép phân giải đệ quy theo hướng top-down:
Ø Bắt đầu từ bài toán lớn phân rã thành bài toán
con.
Ø Đi giải từng bài toán con. Việc giải bài toán con lại đưa về phép phân rã tiếp thành các bài toán con nhỏ hơn.
v Phép phân giải đệ quy theo hướng bottom-up:
Ø Bắt đầu giải các bài toán nhỏ (bài toán cơ sở). Ø Sau đó giải các bài toán lớn hơn (bài toán ban
đầu).
11 9/17/16 Trần Minh Thái - Phạm Đức Thành
Hai loại quy hoạch động
v Ví dụ: tính số hạng thứ n của dãy Fibonaci như
sau:
12 9/17/16 Trần Minh Thái - Phạm Đức Thành
Hai loại quy hoạch động
static int fiBoNaCi_QuyHoach_C1(int n) { int kq, Fn_1, Fn_2; if (n <= 1) kq = 1; else { Fn_1 = fiBoNaCi_QuyHoach_C1(n - 1); Fn_2 = fiBoNaCi_QuyHoach_C1(n - 2); kq = Fn_1 + Fn_2; } return kq; }
13 9/17/16 Trần Minh Thái - Phạm Đức Thành
Hai loại quy hoạch động
static int fiBoNaCi_QuyHoach_C2(int n) { int []Fn=new int[101]; Fn[0] = Fn[1] = 1; for (int i = 2; i <= n; i++) Fn[i] = Fn[i - 1] + Fn[i - 2]; return Fn[n]; }
14 9/17/16 Trần Minh Thái - Phạm Đức Thành
Khái niệm
v Bài toán quy hoạch động: là bài toán được giải
theo phương pháp quy hoạch động.
v Công thức truy hồi của quy hoạch động: là công thức phối hợp nghiệm của các bài toán con để có nghiệm cho bài toán lớn.
v Bảng phương án của quy hoạch động: là Không gian lưu trữ lời giải của các bài toán con để tìm cách phối hợp chúng.
15 9/17/16 Trần Minh Thái - Phạm Đức Thành
Các bước cài đặt
v Cần thỏa mãn các yêu cầu sau:
Ø Phải phân rã được bài toán lớn thành các bài toán con và sự phối hợp lời giải đó cho ta lời giải cuối cùng của bài toán lớn. Ø Phải có đủ không gian bộ nhớ vật lý. Ø Quá trình phối hợp lời giải bài toán con đến bài toán ban đầu, phải có một số bước hữu hạn (tính dừng của chương trình).
16 9/17/16 Trần Minh Thái - Phạm Đức Thành
Các bước cài đặt
v Bước 1: Phân tích bài toán, lập công thức truy
hồi.
v Bước 2: Giải tất cả các bài toán con và lưu vào bảng phương án (dùng mảng một chiều hoặc hai chiều).
v Bước 3: Dùng công thức truy hồi để phối hợp các lời giải của những bài toán con, lặp cho đến khi tìm được lời giải ban đầu.
v Bước 4: Dựa vào bảng phương án, truy vết tìm
lời giải tối ưu.
17 9/17/16 Trần Minh Thái - Phạm Đức Thành
Các bước cài đặt
v Ví dụ: Tính
v B1: Phân tích bài toán, công thức truy hồi:
18 9/17/16 Trần Minh Thái - Phạm Đức Thành
Các bước cài đặt
v B2: Giải bài toán con và lưu vào bảng phương
án
v Bảng phương án với n=4
1
1
1 1 1 1 1 1
1
19 9/17/16
F 0 1 2 3 4 0 1 2 3 4 Trần Minh Thái - Phạm Đức Thành
Các bước cài đặt
v B3: Tính từ dòng i=2 đến n theo công thức truy
hồi sau:
F[i,k]=F[i-1,k]+F[i-1,k-1];
v Bảng phương án sau khi thực hiện B3
2
3
4
1
F 0 1 0 1 1 1 2 1 3 1 4
1 2 3 4
1 4
1
1 3 6 v B4: Kết quả bài toán lưu ở dòng cuối cùng và
cột k
20 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.2] Công thức truy hồi
v Công thức truy hồi của quy hoạch động: là công thức phối hợp nghiệm của các bài toán con để có nghiệm cho bài toán lớn.
v Khi phân tích bài toán và tìm ra công thức truy
hồi, ta sẽ phải tìm ra hai thành phần sau: Ø Phần cơ sở quy hoạch động (giống như phần
cố định – neo trong chương 3 về đệ quy).
Ø Phần truy hồi (công thức truy hồi – giống như
phần đệ quy của chương 3).
21 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.2] Công thức truy hồi
v Ta xét ví dụ sau: Cho số tự nhiên n<=100. Hãy cho biết có bao nhiêu cách phân tích số n thành tổng của dãy các số nguyên dương.
v Với n=5, ta có 7 cách như sau:
1 2 3 4 5 6 7
1+1+1+1+1=5 1+1+1+2=5 1+2+2=5 1+1+3=5 1+4=5 2+3=5 5=5
22 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.2] Công thức truy hồi
v Lưu ý:
Ø Trường hợp n=0 vẫn tính là một cách (dãy
rỗng thì tổng bằng 0).
Ø Không tính hoán các cách phân tích.
v Liệu có cách nào tính ra ngay mà không phải liệt
kê như bảng 4.3 không?
v Nếu n=100 thì có 190.569.292 cách phân tích,
như thế thì rất chậm.
23 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Gọi F[m,v] là số cách phân tích số v thành tổng
các số nguyên dương <= m.
v Các cách phân tích số v thành tổng các số nguyên
dương <= m có thể chia thành hai loại: Ø Loại 1: Không chứa m trong các phân tích: số cách phân tích số v thành tổng các số nguyên dương < m và bằng F[m-1,v].
Ø Loại 2: Có chứa ít nhất một số m trong phân tích, khi đó nếu bỏ m ta sẽ được các cách phân tích số v=m thành tổng các số nguyên dương <= m. Lúc này số cách sẽ bằng F[m,v-m].
24 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.2] Công thức truy hồi
v Trường hợp m>v thì chỉ có loại 1, ngược lại (m<=v) có cả 2 loại. Ta có công thức truy hồi sau:
v Ta xây dựng công thức F[m,v] từ F[m-1,v] và
F[m,v-m], gọi là công thức truy hồi
25 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.2] Công thức truy hồi
v Với n=5, ta có bảng phương án quy hoạch như
sau:
4
2
3
1
F 0
0 1 1 1 1 1
0 1 2 3 3 3
0 1 3 4 5 5
1 1 1 1 1 1
26 9/17/16
5 v 0 0 0 1 1 1 2 2 3 3 2 5 4 2 6 7 2 5 m Trần Minh Thái - Phạm Đức Thành
[4.2] Công thức truy hồi
v Nhìn vào bảng phương án, ta nhận xét rằng
F[m,v] bằng tổng của: Ø Một phần tử ở hàng trên, cùng cột: F[m-1,v]. Ø Một phần tử ở cùng hàng, bên trái cột là v-m:
F[m,v-m].
v Ví dụ:
Ø F[5,5]=F[4,5]+F[5,0]=6+1=7. Ø F[3,5]=F[2,5]+F[3,2]=3+2=5.
27 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.2] Công thức truy hồi
v Nhận xét:
Ø Ta tính dòng trên trước. Ø Trong cùng một dòng thì tính từ trái sang. Ø Cột v=0 thì có một cách. Ø Dòng m=0 thì không có cách nào với mọi v>0.
28 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.2] Công thức truy hồi
static int soCachPhanTichSo(int n) { int[,] F = new int[101, 101]; int m, v; for (m = 0; m <= n; m++) F[m, 0] = 1; for (v = 1; v <= n; v++) F[0, v] = 0; for (m = 1; m <= n; m++) for (v = 1; v <= n; v++) if (v < m) F[m, v] = F[m - 1, v]; else F[m, v] = F[m - 1, v]+ F[m,v-m]; return F[n, n]; }
29 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.3] Một số bài toán quy hoạch động v Bài toán tìm dãy con đơn điệu tăng dài nhất. v Bài toán chiếc ba lô dạng một. v ....
30 9/17/16 Trần Minh Thái - Phạm Đức Thành
Tìm dãy con đơn điệu tăng dài nhất v Mô tả: Cho dãy số nguyên A gồm n phần tử. Một dãy con của A là một cách chọn trong A một số phần tử giữ nguyên thứ tự (ta có tổng cộng 2n dãy con). Hãy tìm dãy con đơn điệu tăng của A có độ dài lớn nhất. v Ví dụ: dãy A={5,2,3,4,9,10,5,6,7,8}. v Dãy con đơn điệu
tăng dài nhất
là
{2,3,4,5,6,7,8}.
31 9/17/16 Trần Minh Thái - Phạm Đức Thành
v B1: Phân tích và công thức truy hồi: v Bổ sung vào dãy A một phần tử ở đầu A[0] có giá và một phần vào cuối dãy A[n+1] có giá trị . Như thế dãy đơn điệu sẽ bắt đầu từ A[0] và
trị -(cid:0) là +(cid:0) kết thúc là A[n+1].
v Tạo thêm dãy phụ có tên L với kích thước bằng dãy A, với mỗi phần tử dãy L[i] có giá trị là độ dài dãy con đơn điệu tăng dài nhất bắt đầu tại A[i] (0<=i<=n+1).
v Ta tính tất cả các L[i] này. v Kết quả bài toán là tìm giá trị lớn nhất trên dãy L
này (L[vtmax]).
32 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Cơ sở quy hoạch động (bài toán nhỏ nhất) v Trường hợp đặc biệt: L[n+1] là độ dài dãy con đơn điệu tăng dần dài nhất bắt đầu tại A[n+1] = +(cid:0)
.
v Vậy dãy con này chỉ có một phần tử là +(cid:0)
,
nên L[n+1]=1.
33 9/17/16 Trần Minh Thái - Phạm Đức Thành
Công thức truy hồi: v Tính L[i] với i chạy từ n trở về 0. Giá trị L[i]
được tính khi khi L[i+1],.., L[n+1] đã biết.
v Phần tử đang xét của dãy A là A[i] sẽ được tính
vào dãy con đơn điệu dài nhất nếu:
Ø A[i]
vị trí sau i, nghĩa là j đi từ i+1 đến n+1.
Ø Chọn ra chỉ số jmax có L[jmax] là lớn nhất.
34 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Công thức truy hồi sau:
v L[i] = L[jmax] + 1
v hoặc: L[i]= max{L[j]+1, với
i
a[i]
35 9/17/16 Trần Minh Thái - Phạm Đức Thành
B2: Lập bảng phương án:
v Tạo thêm dãy phụ T để lưu vị trí kế tiếp của của
A[i] trong dãy con đơn điệu dài nhất: T[i]=jmax,
với A[jmax] là phần tử kế tiếp của A[i].
v Ta có bảng phương án sau:
0
1
2
3
4
5
6
7
8
9
10
i
A[i]
(cid:0)
5
2
3
4
9
10
5
6
7
8
11
+(cid:0)
L[i]
9
5
8
7
6
3
2
5
4
3
2
1
2
8
3
4
7
6
11
8
9
10
11
T[i]
36 9/17/16 Trần Minh Thái - Phạm Đức Thành
B3: Truy vết:
v Sau khi tính đồng hành hai dãy L và T, ta sẽ bắt
đầu từ T[0] và có kết quả như sau:
T[T[T[0]]] (cid:0)
T[T[0]] (cid:0)
T[0] (cid:0)
...
v Thuật toán truy vết như sau:
T[0]
i (cid:0)
while i ≠ n+1 do
{
write A[i];
i (cid:0)
T[i];
}
37 9/17/16 Trần Minh Thái - Phạm Đức Thành
Ví dụ
DATA.INP
DAYCONTANG.OUT
1
10
7
2
5 2 3 4 9 10 5 6 7 8
2 3 4 5 6 7 8
v Tập tin DATA.INP:
Ø Dòng 1: Số phần tử của dãy n=10.
Ø Dòng 2: n (10) số cách nhau bởi khoảng
trắng.
v Tập tin DAYCONTANG.OUT:
Ø Dòng 1: Độ dài dãy con tăng.
Ø Dòng 2: các phần tử trong dãy con tăng.
38 9/17/16 Trần Minh Thái - Phạm Đức Thành
static bool docFile(ref int[]A,string fileName)
{ StreamReader sr = new StreamReader(fileName);
if( sr == null)
{ Console.WriteLine("Loi khi doc file"); return
false; }
int n = int.Parse(sr.ReadLine()); A = new int[n + 2];
string S = sr.ReadLine();
string[] M = S.Split(new Char[] { ' ' }); int j = 0;
for (int i = 1; i <= n; i++)
{ while (M[j] == "") j++;
A[i] = int.Parse(M[j++]);
}
return true;
}
39 9/17/16 Trần Minh Thái - Phạm Đức Thành
0
(cid:0)
11
+(cid:0)
1
6
10
2
11
4
4
6
7
1
5
5
8
3
3
7
4
5
9
3
6
9
2
7
5
5
8
i
A[i]
L[i]
T[i]
2
2
8
3
taoBangPhuongAn(int[]A,out
8
6
4
9
int
10
9
8
7
2
3
11
10
[]L,out
static void
int[]T)
{ int n = A.Length;
L = new int[n]; T = new int[n];
A[0] = int.MinValue;
A[n - 1] = int.MaxValue;
40 Trần Minh Thái - Phạm Đức Thành
L[n - 1] = 1;
for(int i= n-2; i>=0; i--)
{ int jmax = n - 1;
for (int j = i + 1; j <= n - 1; j++)
if (A[j] > A[i] && L[j] > L[jmax])
jmax = j;
L[i] = L[jmax] + 1; T[i] = jmax;
}
}9/17/16
0
(cid:0)
11
+(cid:0)
1
9
2
1
5
5
8
2
2
8
3
3
3
7
4
4
4
6
7
5
9
3
6
6
10
2
11
7
5
5
8
8
6
4
9
9
7
3
10
10
8
2
11
i
A[i]
L[i]
T[i]
static bool truyVet (int[] A, int[] L, int[] T, string
fileName)
{
StreamWriter sw = new StreamWriter(fileName);
41 Trần Minh Thái - Phạm Đức Thành
if(sw==null)
{Console.WriteLine("Khong ghi duoc file");return
false; }
sw.WriteLine("{0}", L[0] - 2); int i = T[0];
while(i
static void Main(string[] args)
{
int[] A = null, L, T;
if(docFile(ref A,"DATA.INP")==true)
{
taoBangPhuongAn(A, out L, out T);
if (truyVet (A, L, T, "DAYCONTANG.OUT") ==
true)
Console.WriteLine("Luu file thanh cong")
}
}
42 9/17/16 Trần Minh Thái - Phạm Đức Thành
Bài toán chiếc ba lô dạng một
Mô tả:
v Có n món đồ, vật thứ i có trọng lượng là wi và
giá trị vi.
v Hãy chọn ra các món có thể bỏ vào ba lô có
trọng lượng tối đa là W sao cho tổng các giá trị
các món đồ là lớn nhất.
43 9/17/16 Trần Minh Thái - Phạm Đức Thành
Cách giải
v Gọi F[i, j] là giá trị lớn nhất có thể có bằng
cách chọn trong các món {1,2,..,j} với giới hạn
trọng lượng j
v Như vậy F[n, W] chính là giá trị lớn nhất khi
được chọn trong số n gói với giới hạn trọng
lượng W
44 9/17/16 Trần Minh Thái - Phạm Đức Thành
B1: Công thức truy hồi tính F[i, j]
v Với giới hạn trọng lượng j, việc chọn phương án
tối ưu trong số các gói {1, 2, .., i-1, i}, để có giá
trị lớn nhất có 2 khả năng:
Ø Không chọn gói thứ i: F[i, j] = F[i-1, j].
Ø Chọn gói thứ i (wi<=j): F[i, j]=vi + F[i-1, j – wi].
Chọn F[i, j] là giá trị lớn nhất trong hai giá trị thu
được ở trên.
v Cơ sở quy hoạch động:
F[0, j] = 0 với mọi j
45 9/17/16 Trần Minh Thái - Phạm Đức Thành
v B2:
Lập
bảng
phương án:
...
F 0 1 2
0
1
2
... ... ... ...
n
... W
...
...
...
...
...
ộ
v B ng F: n+1 dòng, W+1 c t
ộ ằ
ơ ở
ạ
ộ
ầ
ứ
ứ
ế
ả
v Dòng đ u tiên: c s quy ho ch đ ng, toàn b b ng 0
ồ
ứ
v Dòng th hai đ n dòng th n: dùng công th c truy h i
46 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng đầu tiên:
9
0
10 11
0
0
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1
2
3
4
5
47 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=1:
9
0
3
10 11
0
0
3
3
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 3 3 3 3 3 3
2
3
4
5
48 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=2:
9
0
3
7
10 11
0
0
3
3
7
7
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 3 3 3 3 3 3
2 0 0 0 3 4 4 4 7 7
3
4
5
49 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=3:
9
0
3
7
8
10 11
0
0
3
3
7
7
8
8
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 3 3 3 3 3 3
2 0 0 0 3 4 4 4 7 7
3 0 0 0 3 4 4 4 7 7
4
5
50 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=4:
9
0
3
7
8
F 0 1 2 3 4 5 6 7 8
10 11
0 0 0 0 0 0 0 0 0 0
0
0
1 0 0 0 3 3 3 3 3 3
3
3
2 0 0 0 3 4 4 4 7 7
7
7
3 0 0 0 3 4 4 4 7 7
8
8
4 0 0 0 3 4 4 4 7 7 10 10 10
5
51 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=5:
9
0
3
7
8
F 0 1 2 3 4 5 6 7 8
10 11
0 0 0 0 0 0 0 0 0 0
0
0
1 0 0 0 3 3 3 3 3 3
3
3
2 0 0 0 3 4 4 4 7 7
7
7
3 0 0 0 3 4 4 4 7 7
8
8
4 0 0 0 3 4 4 4 7 7 10 10 10
5 0 0 0 3 4 4 4 7 8 10 10 11
52 9/17/16 Trần Minh Thái - Phạm Đức Thành
B3: Truy vết
v Từ F[n, W]:
Ø Nếu F[n,W]=F[n-1, W] thì không chọn gói
n. Xét tiếp F[n-1, W].
Ø Ngược lại (F[n, W] ≠ F[n-1, W]) thì chọn gói
thứ n. Xét tiếp F[n-1, W-wn].
v Lặp lại cho đến dòng đầu tiên của bảng
phương án.
53 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Tập tin BALO.INP:
Ø Dòng 1: số n và
BALO.INP BALO.OUT
11
5 11
1
W.
5 2 1
2
3 3
3
4 4
Ø n dòng tiếp theo:
dòng thứ i chứa 2
số wi, vi.
v Tập tin BALO.OUT:
4
5 4
5
9 10
Ø Dòng 1: Giá trị lớn
nhất có thể bỏ
vào ba lô.
6
4 4
Ø Dòng 2: chỉ số đồ
vật được lấy bỏ
vào ba lô.
54 9/17/16 Trần Minh Thái - Phạm Đức Thành
55 Trần Minh Thái - Phạm Đức Thành
static bool docFile(ref int[] w, ref int[]v, ref int n, ref int W,
string fileName)
{ StreamReader sr = new StreamReader(fileName);
string S = sr.ReadLine();
string[] M = S.Split(new Char[] { ' ' }); int j = 0;
while (M[j] == "") j++; n = int.Parse(M[j++]);
while (M[j] == "") j++; W = int.Parse(M[j++]);
w = new int[n + 1]; v = new int[n + 1];
for (int i = 0; i < n; i++)
{ S = sr.ReadLine(); M = S.Split(new Char[] { ' ' }); j =
0;
while (M[j] == "") j++; w[i] = int.Parse(M[j++]);
while (M[j] == "") j++; v[i] = int.Parse(M[j++]);
}
return true;
} 9/17/16
56
static void bangPhuongAn(int[] w, int[] v, int n, int W, out
int[,] F)
{
F = new int[n + 1, W + 1];
for (int j = 0; j <= W; j++)
F[0, j] = 0;
for(int i=1; i<= n; i++)
for(int j=0; j<= W; j++)
{
F[i, j] = F[i - 1, j];
if (j >= w[i - 1] && F[i, j] < F[i - 1, j - w[i - 1]] + v[i -
1])
F[i, j] = F[i - 1, j - w[i - 1]] + v[i - 1];
}
} 9/17/16
Trần Minh Thái - Phạm Đức Thành
static bool truyVet (int[]w, int[]v, int n, int W, int[,]F, string
fName)
{
StreamWriter sw = new StreamWriter(fName);
57
sw.WriteLine("{0}", F[n,W]);
while (n>0)
{ if (F[n, W] != F[n - 1, W])
{ sw.Write("{0,4}", n);
W = W - w[n-1];
}
n--;
}
sw.Close();
return true;
} 9/17/16
Trần Minh Thái - Phạm Đức Thành
static void Main(string[] args)
{
int[] w=null, v=null; int n=0, W=0; int[,] F;
if (docFile(ref w,ref v,ref n,ref W,"..//..//BALO.INP")
==true)
{
bangPhuongAn(w, v, n, W, out F);
if (truyVet (w,v,n,W,F,"..//..//BALO.OUT") == true)
Console.WriteLine("Luu file thanh cong");
}
Console.ReadLine();
}
58 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Phương pháp quy hoạch động do nhà toán
học Richard Bellman phát minh vào năm
1953.
v Ý tưởng của nguyên lý tối ưu Bellman là:
Ø “Với mỗi quá trình điều khiển tối ưu, đối
với trạng thái bắt đầu A0, với trạng thái A
trong quá trình đó, phần quá trình kể từ
trạng thái A xem như trạng thái bắt đầu
cũng là tối ưu”.
59 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Phương pháp quy hoạch động thường được
dùng để giải các bài toán tối ưu có bản chất
là đệ quy:
Ø Việc tìm phương án tối ưu có thể đưa về
tìm tối ưu cho các bài toán con hữu hạn.
Ø Thuật toán đệ quy đã tìm hiểu ở chương 3
đa số là dùng nguyên lý “chia để trị” và
trong quy hoạch động cũng áp dụng
nguyên lý này.
60 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Có 2 loại quy hoạch động:
Ø Phép phân giải đệ quy theo hướng “từ trên
xuống” (top-down).
Ø Phép phân giải đệ quy theo hướng “từ
dưới lên” (bottom-up).
61 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Ta có một số khái niệm sau:
Ø Bài toán quy hoạch động: giải theo
phương pháp quy hoạch động.
Ø Công thức truy hồi của quy hoạch động: là
công thức phối hợp nghiệm của các bài
toán con để có nghiệm cho bài toán lớn.
Ø Bảng phương án của quy hoạch động: là
không gian lưu trữ lời giải của các bài toán
con để tìm cách phối hợp chúng.
62 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Muốn giải bằng phương pháp quy hoạch
động, bài toán cần thỏa mãn các yêu cầu
sau:
Ø Phải phân rã được bài toán lớn thành các
bài toán con và sự phối hợp lời giải đó cho
ta lời giải cuối cùng của bài toán lớn.
Ø Phải có đủ không gian bộ nhớ vật lý.
Ø Quá trình phối hợp lời giải bài toán con
đến bài toán ban đầu, phải có một số bước
hữu hạn (tính dừng của chương trình).
63 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Các bước cài đặt:
Ø Bước 1: Phân tích bài toán, lập công thức
truy hồi.
Ø Bước 2: Giải tất cả các bài toán con và lưu
vào bảng phương án (dùng mảng một chiều
hoặc hai chiều).
Ø Bước 3: Dùng công thức truy hồi để phối
hợp các lời giải của những bài toán con, lặp
cho đến khi tìm được lời giải ban đầu.
Ø Bước 4: Dựa vào bảng phương án, truy vết
tìm lời giải tối ưu.
64 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Cũng gần giống như phần đệ quy ở chương 3:
khi phân tích bài toán và tìm ra công thức truy
hồi, ta sẽ phải tìm ra hai thành phần sau:
Ø Phần cơ sở quy hoạch động (giống như phần
cố định – neo trong chương 3 về đệ quy).
Ø Phần truy hồi (công thức truy hồi – giống
như phần đệ quy của chương 3).
65 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập
Bài 1: Bài toán bố trí phòng họp
v Có n cuộc họp, cuộc họp thứ i bắt đầu vào thời
điểm si và kết thúc fi.
v Do chỉ có một phòng hội thảo nên hai cuộc họp
bất kỳ sẽ được cùng bố trí phục vụ nếu khoảng
thời gian làm việc của các cuộc họp này chỉ
giao nhau tại các đầu mút.
v Hãy bố trí lịch họp sao cho phục vụ được nhiều
cuộc họp nhất.
66 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập
Bài 2: Bài toán điền dấu biểu thức
v Cho n số tự nhiên a1, a2, .., an. Ban đầu các số
được đặt liên tiếp theo đúng thứ tự cách nhau
bởi dấu chấm hỏi (?) như sau: a1 ? a2 ? .. ? ,
an.
v Cho trước số nguyên S, có cách nào thay các
dấu chấm hỏi bằng dấu công (+) hoặc trừ (-) để
được một biểu thức số học cho giá trị là S
không?
v Ví dụ: dãy ban đầu 1 ? 2? 3 ? 4 với K=0, thì cho
kết quả 1-2-3+4 = 0.
67 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập
Bài 3: Bài toán xâu con chung dài nhất.
v Xâu ký tự S gọi là xâu con của xâu M nếu có thể
xóa bớt một số ký tự trong xâu M để được xâu
S.
v Nhập vào hai xâu ký tự X, Y và tìm xâu Z có độ
dài lớn là xâu con của cả X và Y.
v Ví dụ: nhập X= “abcdefghi123” và Y=
“abc1def2ghi3” thì Z là “abcdefghi3”.
68 9/17/16 Trần Minh Thái - Phạm Đức Thành
vị trí sau i, nghĩa là j đi từ i+1 đến n+1.
Ø Chọn ra chỉ số jmax có L[jmax] là lớn nhất.
34 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Công thức truy hồi sau: v L[i] = L[jmax] + 1 v hoặc: L[i]= max{L[j]+1, với
i
a[i]
35 9/17/16 Trần Minh Thái - Phạm Đức Thành
B2: Lập bảng phương án:
v Tạo thêm dãy phụ T để lưu vị trí kế tiếp của của
A[i] trong dãy con đơn điệu dài nhất: T[i]=jmax,
với A[jmax] là phần tử kế tiếp của A[i].
v Ta có bảng phương án sau:
0
1
2
3
4
5
6
7
8
9
10
i
A[i]
(cid:0)
5
2
3
4
9
10
5
6
7
8
11
+(cid:0)
L[i]
9
5
8
7
6
3
2
5
4
3
2
1
2
8
3
4
7
6
11
8
9
10
11
T[i]
36 9/17/16 Trần Minh Thái - Phạm Đức Thành
B3: Truy vết:
v Sau khi tính đồng hành hai dãy L và T, ta sẽ bắt
đầu từ T[0] và có kết quả như sau:
T[T[T[0]]] (cid:0)
T[T[0]] (cid:0)
T[0] (cid:0)
...
v Thuật toán truy vết như sau:
T[0]
i (cid:0)
while i ≠ n+1 do
{
write A[i];
i (cid:0)
T[i];
}
37 9/17/16 Trần Minh Thái - Phạm Đức Thành
Ví dụ
DATA.INP
DAYCONTANG.OUT
1
10
7
2
5 2 3 4 9 10 5 6 7 8
2 3 4 5 6 7 8
v Tập tin DATA.INP:
Ø Dòng 1: Số phần tử của dãy n=10.
Ø Dòng 2: n (10) số cách nhau bởi khoảng
trắng.
v Tập tin DAYCONTANG.OUT:
Ø Dòng 1: Độ dài dãy con tăng.
Ø Dòng 2: các phần tử trong dãy con tăng.
38 9/17/16 Trần Minh Thái - Phạm Đức Thành
static bool docFile(ref int[]A,string fileName)
{ StreamReader sr = new StreamReader(fileName);
if( sr == null)
{ Console.WriteLine("Loi khi doc file"); return
false; }
int n = int.Parse(sr.ReadLine()); A = new int[n + 2];
string S = sr.ReadLine();
string[] M = S.Split(new Char[] { ' ' }); int j = 0;
for (int i = 1; i <= n; i++)
{ while (M[j] == "") j++;
A[i] = int.Parse(M[j++]);
}
return true;
}
39 9/17/16 Trần Minh Thái - Phạm Đức Thành
0
(cid:0)
11
+(cid:0)
1
6
10
2
11
4
4
6
7
1
5
5
8
3
3
7
4
5
9
3
6
9
2
7
5
5
8
i
A[i]
L[i]
T[i]
2
2
8
3
taoBangPhuongAn(int[]A,out
8
6
4
9
int
10
9
8
7
2
3
11
10
[]L,out
static void
int[]T)
{ int n = A.Length;
L = new int[n]; T = new int[n];
A[0] = int.MinValue;
A[n - 1] = int.MaxValue;
40 Trần Minh Thái - Phạm Đức Thành
L[n - 1] = 1;
for(int i= n-2; i>=0; i--)
{ int jmax = n - 1;
for (int j = i + 1; j <= n - 1; j++)
if (A[j] > A[i] && L[j] > L[jmax])
jmax = j;
L[i] = L[jmax] + 1; T[i] = jmax;
}
}9/17/16
0
(cid:0)
11
+(cid:0)
1
9
2
1
5
5
8
2
2
8
3
3
3
7
4
4
4
6
7
5
9
3
6
6
10
2
11
7
5
5
8
8
6
4
9
9
7
3
10
10
8
2
11
i
A[i]
L[i]
T[i]
static bool truyVet (int[] A, int[] L, int[] T, string
fileName)
{
StreamWriter sw = new StreamWriter(fileName);
41 Trần Minh Thái - Phạm Đức Thành
if(sw==null)
{Console.WriteLine("Khong ghi duoc file");return
false; }
sw.WriteLine("{0}", L[0] - 2); int i = T[0];
while(i
static void Main(string[] args)
{
int[] A = null, L, T;
if(docFile(ref A,"DATA.INP")==true)
{
taoBangPhuongAn(A, out L, out T);
if (truyVet (A, L, T, "DAYCONTANG.OUT") ==
true)
Console.WriteLine("Luu file thanh cong")
}
}
42 9/17/16 Trần Minh Thái - Phạm Đức Thành
Bài toán chiếc ba lô dạng một
Mô tả:
v Có n món đồ, vật thứ i có trọng lượng là wi và
giá trị vi.
v Hãy chọn ra các món có thể bỏ vào ba lô có
trọng lượng tối đa là W sao cho tổng các giá trị
các món đồ là lớn nhất.
43 9/17/16 Trần Minh Thái - Phạm Đức Thành
Cách giải
v Gọi F[i, j] là giá trị lớn nhất có thể có bằng
cách chọn trong các món {1,2,..,j} với giới hạn
trọng lượng j
v Như vậy F[n, W] chính là giá trị lớn nhất khi
được chọn trong số n gói với giới hạn trọng
lượng W
44 9/17/16 Trần Minh Thái - Phạm Đức Thành
B1: Công thức truy hồi tính F[i, j]
v Với giới hạn trọng lượng j, việc chọn phương án
tối ưu trong số các gói {1, 2, .., i-1, i}, để có giá
trị lớn nhất có 2 khả năng:
Ø Không chọn gói thứ i: F[i, j] = F[i-1, j].
Ø Chọn gói thứ i (wi<=j): F[i, j]=vi + F[i-1, j – wi].
Chọn F[i, j] là giá trị lớn nhất trong hai giá trị thu
được ở trên.
v Cơ sở quy hoạch động:
F[0, j] = 0 với mọi j
45 9/17/16 Trần Minh Thái - Phạm Đức Thành
v B2:
Lập
bảng
phương án:
...
F 0 1 2
0
1
2
... ... ... ...
n
... W
...
...
...
...
...
ộ
v B ng F: n+1 dòng, W+1 c t
ộ ằ
ơ ở
ạ
ộ
ầ
ứ
ứ
ế
ả
v Dòng đ u tiên: c s quy ho ch đ ng, toàn b b ng 0
ồ
ứ
v Dòng th hai đ n dòng th n: dùng công th c truy h i
46 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng đầu tiên:
9
0
10 11
0
0
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1
2
3
4
5
47 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=1:
9
0
3
10 11
0
0
3
3
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 3 3 3 3 3 3
2
3
4
5
48 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=2:
9
0
3
7
10 11
0
0
3
3
7
7
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 3 3 3 3 3 3
2 0 0 0 3 4 4 4 7 7
3
4
5
49 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=3:
9
0
3
7
8
10 11
0
0
3
3
7
7
8
8
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 3 3 3 3 3 3
2 0 0 0 3 4 4 4 7 7
3 0 0 0 3 4 4 4 7 7
4
5
50 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=4:
9
0
3
7
8
F 0 1 2 3 4 5 6 7 8
10 11
0 0 0 0 0 0 0 0 0 0
0
0
1 0 0 0 3 3 3 3 3 3
3
3
2 0 0 0 3 4 4 4 7 7
7
7
3 0 0 0 3 4 4 4 7 7
8
8
4 0 0 0 3 4 4 4 7 7 10 10 10
5
51 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=5:
9
0
3
7
8
F 0 1 2 3 4 5 6 7 8
10 11
0 0 0 0 0 0 0 0 0 0
0
0
1 0 0 0 3 3 3 3 3 3
3
3
2 0 0 0 3 4 4 4 7 7
7
7
3 0 0 0 3 4 4 4 7 7
8
8
4 0 0 0 3 4 4 4 7 7 10 10 10
5 0 0 0 3 4 4 4 7 8 10 10 11
52 9/17/16 Trần Minh Thái - Phạm Đức Thành
B3: Truy vết
v Từ F[n, W]:
Ø Nếu F[n,W]=F[n-1, W] thì không chọn gói
n. Xét tiếp F[n-1, W].
Ø Ngược lại (F[n, W] ≠ F[n-1, W]) thì chọn gói
thứ n. Xét tiếp F[n-1, W-wn].
v Lặp lại cho đến dòng đầu tiên của bảng
phương án.
53 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Tập tin BALO.INP:
Ø Dòng 1: số n và
BALO.INP BALO.OUT
11
5 11
1
W.
5 2 1
2
3 3
3
4 4
Ø n dòng tiếp theo:
dòng thứ i chứa 2
số wi, vi.
v Tập tin BALO.OUT:
4
5 4
5
9 10
Ø Dòng 1: Giá trị lớn
nhất có thể bỏ
vào ba lô.
6
4 4
Ø Dòng 2: chỉ số đồ
vật được lấy bỏ
vào ba lô.
54 9/17/16 Trần Minh Thái - Phạm Đức Thành
55 Trần Minh Thái - Phạm Đức Thành
static bool docFile(ref int[] w, ref int[]v, ref int n, ref int W,
string fileName)
{ StreamReader sr = new StreamReader(fileName);
string S = sr.ReadLine();
string[] M = S.Split(new Char[] { ' ' }); int j = 0;
while (M[j] == "") j++; n = int.Parse(M[j++]);
while (M[j] == "") j++; W = int.Parse(M[j++]);
w = new int[n + 1]; v = new int[n + 1];
for (int i = 0; i < n; i++)
{ S = sr.ReadLine(); M = S.Split(new Char[] { ' ' }); j =
0;
while (M[j] == "") j++; w[i] = int.Parse(M[j++]);
while (M[j] == "") j++; v[i] = int.Parse(M[j++]);
}
return true;
} 9/17/16
56
static void bangPhuongAn(int[] w, int[] v, int n, int W, out
int[,] F)
{
F = new int[n + 1, W + 1];
for (int j = 0; j <= W; j++)
F[0, j] = 0;
for(int i=1; i<= n; i++)
for(int j=0; j<= W; j++)
{
F[i, j] = F[i - 1, j];
if (j >= w[i - 1] && F[i, j] < F[i - 1, j - w[i - 1]] + v[i -
1])
F[i, j] = F[i - 1, j - w[i - 1]] + v[i - 1];
}
} 9/17/16
Trần Minh Thái - Phạm Đức Thành
static bool truyVet (int[]w, int[]v, int n, int W, int[,]F, string
fName)
{
StreamWriter sw = new StreamWriter(fName);
57
sw.WriteLine("{0}", F[n,W]);
while (n>0)
{ if (F[n, W] != F[n - 1, W])
{ sw.Write("{0,4}", n);
W = W - w[n-1];
}
n--;
}
sw.Close();
return true;
} 9/17/16
Trần Minh Thái - Phạm Đức Thành
static void Main(string[] args)
{
int[] w=null, v=null; int n=0, W=0; int[,] F;
if (docFile(ref w,ref v,ref n,ref W,"..//..//BALO.INP")
==true)
{
bangPhuongAn(w, v, n, W, out F);
if (truyVet (w,v,n,W,F,"..//..//BALO.OUT") == true)
Console.WriteLine("Luu file thanh cong");
}
Console.ReadLine();
}
58 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Phương pháp quy hoạch động do nhà toán
học Richard Bellman phát minh vào năm
1953.
v Ý tưởng của nguyên lý tối ưu Bellman là:
Ø “Với mỗi quá trình điều khiển tối ưu, đối
với trạng thái bắt đầu A0, với trạng thái A
trong quá trình đó, phần quá trình kể từ
trạng thái A xem như trạng thái bắt đầu
cũng là tối ưu”.
59 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Phương pháp quy hoạch động thường được
dùng để giải các bài toán tối ưu có bản chất
là đệ quy:
Ø Việc tìm phương án tối ưu có thể đưa về
tìm tối ưu cho các bài toán con hữu hạn.
Ø Thuật toán đệ quy đã tìm hiểu ở chương 3
đa số là dùng nguyên lý “chia để trị” và
trong quy hoạch động cũng áp dụng
nguyên lý này.
60 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Có 2 loại quy hoạch động:
Ø Phép phân giải đệ quy theo hướng “từ trên
xuống” (top-down).
Ø Phép phân giải đệ quy theo hướng “từ
dưới lên” (bottom-up).
61 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Ta có một số khái niệm sau:
Ø Bài toán quy hoạch động: giải theo
phương pháp quy hoạch động.
Ø Công thức truy hồi của quy hoạch động: là
công thức phối hợp nghiệm của các bài
toán con để có nghiệm cho bài toán lớn.
Ø Bảng phương án của quy hoạch động: là
không gian lưu trữ lời giải của các bài toán
con để tìm cách phối hợp chúng.
62 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Muốn giải bằng phương pháp quy hoạch
động, bài toán cần thỏa mãn các yêu cầu
sau:
Ø Phải phân rã được bài toán lớn thành các
bài toán con và sự phối hợp lời giải đó cho
ta lời giải cuối cùng của bài toán lớn.
Ø Phải có đủ không gian bộ nhớ vật lý.
Ø Quá trình phối hợp lời giải bài toán con
đến bài toán ban đầu, phải có một số bước
hữu hạn (tính dừng của chương trình).
63 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Các bước cài đặt:
Ø Bước 1: Phân tích bài toán, lập công thức
truy hồi.
Ø Bước 2: Giải tất cả các bài toán con và lưu
vào bảng phương án (dùng mảng một chiều
hoặc hai chiều).
Ø Bước 3: Dùng công thức truy hồi để phối
hợp các lời giải của những bài toán con, lặp
cho đến khi tìm được lời giải ban đầu.
Ø Bước 4: Dựa vào bảng phương án, truy vết
tìm lời giải tối ưu.
64 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Cũng gần giống như phần đệ quy ở chương 3:
khi phân tích bài toán và tìm ra công thức truy
hồi, ta sẽ phải tìm ra hai thành phần sau:
Ø Phần cơ sở quy hoạch động (giống như phần
cố định – neo trong chương 3 về đệ quy).
Ø Phần truy hồi (công thức truy hồi – giống
như phần đệ quy của chương 3).
65 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập
Bài 1: Bài toán bố trí phòng họp
v Có n cuộc họp, cuộc họp thứ i bắt đầu vào thời
điểm si và kết thúc fi.
v Do chỉ có một phòng hội thảo nên hai cuộc họp
bất kỳ sẽ được cùng bố trí phục vụ nếu khoảng
thời gian làm việc của các cuộc họp này chỉ
giao nhau tại các đầu mút.
v Hãy bố trí lịch họp sao cho phục vụ được nhiều
cuộc họp nhất.
66 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập
Bài 2: Bài toán điền dấu biểu thức
v Cho n số tự nhiên a1, a2, .., an. Ban đầu các số
được đặt liên tiếp theo đúng thứ tự cách nhau
bởi dấu chấm hỏi (?) như sau: a1 ? a2 ? .. ? ,
an.
v Cho trước số nguyên S, có cách nào thay các
dấu chấm hỏi bằng dấu công (+) hoặc trừ (-) để
được một biểu thức số học cho giá trị là S
không?
v Ví dụ: dãy ban đầu 1 ? 2? 3 ? 4 với K=0, thì cho
kết quả 1-2-3+4 = 0.
67 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập
Bài 3: Bài toán xâu con chung dài nhất.
v Xâu ký tự S gọi là xâu con của xâu M nếu có thể
xóa bớt một số ký tự trong xâu M để được xâu
S.
v Nhập vào hai xâu ký tự X, Y và tìm xâu Z có độ
dài lớn là xâu con của cả X và Y.
v Ví dụ: nhập X= “abcdefghi123” và Y=
“abc1def2ghi3” thì Z là “abcdefghi3”.
68 9/17/16 Trần Minh Thái - Phạm Đức Thành
a[i]
35 9/17/16 Trần Minh Thái - Phạm Đức Thành
B2: Lập bảng phương án:
v Tạo thêm dãy phụ T để lưu vị trí kế tiếp của của
A[i] trong dãy con đơn điệu dài nhất: T[i]=jmax,
với A[jmax] là phần tử kế tiếp của A[i].
v Ta có bảng phương án sau:
0
1
2
3
4
5
6
7
8
9
10
i
A[i]
(cid:0)
5
2
3
4
9
10
5
6
7
8
11
+(cid:0)
L[i]
9
5
8
7
6
3
2
5
4
3
2
1
2
8
3
4
7
6
11
8
9
10
11
T[i]
36 9/17/16 Trần Minh Thái - Phạm Đức Thành
B3: Truy vết:
v Sau khi tính đồng hành hai dãy L và T, ta sẽ bắt
đầu từ T[0] và có kết quả như sau:
T[T[T[0]]] (cid:0)
T[T[0]] (cid:0)
T[0] (cid:0)
...
v Thuật toán truy vết như sau:
T[0]
i (cid:0)
while i ≠ n+1 do
{
write A[i];
i (cid:0)
T[i];
}
37 9/17/16 Trần Minh Thái - Phạm Đức Thành
Ví dụ
DATA.INP
DAYCONTANG.OUT
1
10
7
2
5 2 3 4 9 10 5 6 7 8
2 3 4 5 6 7 8
v Tập tin DATA.INP:
Ø Dòng 1: Số phần tử của dãy n=10.
Ø Dòng 2: n (10) số cách nhau bởi khoảng
trắng.
v Tập tin DAYCONTANG.OUT:
Ø Dòng 1: Độ dài dãy con tăng.
Ø Dòng 2: các phần tử trong dãy con tăng.
38 9/17/16 Trần Minh Thái - Phạm Đức Thành
static bool docFile(ref int[]A,string fileName)
{ StreamReader sr = new StreamReader(fileName);
if( sr == null)
{ Console.WriteLine("Loi khi doc file"); return
false; }
int n = int.Parse(sr.ReadLine()); A = new int[n + 2];
string S = sr.ReadLine();
string[] M = S.Split(new Char[] { ' ' }); int j = 0;
for (int i = 1; i <= n; i++)
{ while (M[j] == "") j++;
A[i] = int.Parse(M[j++]);
}
return true;
}
39 9/17/16 Trần Minh Thái - Phạm Đức Thành
0
(cid:0)
11
+(cid:0)
1
6
10
2
11
4
4
6
7
1
5
5
8
3
3
7
4
5
9
3
6
9
2
7
5
5
8
i
A[i]
L[i]
T[i]
2
2
8
3
taoBangPhuongAn(int[]A,out
8
6
4
9
int
10
9
8
7
2
3
11
10
[]L,out
static void
int[]T)
{ int n = A.Length;
L = new int[n]; T = new int[n];
A[0] = int.MinValue;
A[n - 1] = int.MaxValue;
40 Trần Minh Thái - Phạm Đức Thành
L[n - 1] = 1;
for(int i= n-2; i>=0; i--)
{ int jmax = n - 1;
for (int j = i + 1; j <= n - 1; j++)
if (A[j] > A[i] && L[j] > L[jmax])
jmax = j;
L[i] = L[jmax] + 1; T[i] = jmax;
}
}9/17/16
0
(cid:0)
11
+(cid:0)
1
9
2
1
5
5
8
2
2
8
3
3
3
7
4
4
4
6
7
5
9
3
6
6
10
2
11
7
5
5
8
8
6
4
9
9
7
3
10
10
8
2
11
i
A[i]
L[i]
T[i]
static bool truyVet (int[] A, int[] L, int[] T, string
fileName)
{
StreamWriter sw = new StreamWriter(fileName);
41 Trần Minh Thái - Phạm Đức Thành
if(sw==null)
{Console.WriteLine("Khong ghi duoc file");return
false; }
sw.WriteLine("{0}", L[0] - 2); int i = T[0];
while(i
static void Main(string[] args)
{
int[] A = null, L, T;
if(docFile(ref A,"DATA.INP")==true)
{
taoBangPhuongAn(A, out L, out T);
if (truyVet (A, L, T, "DAYCONTANG.OUT") ==
true)
Console.WriteLine("Luu file thanh cong")
}
}
42 9/17/16 Trần Minh Thái - Phạm Đức Thành
Bài toán chiếc ba lô dạng một
Mô tả:
v Có n món đồ, vật thứ i có trọng lượng là wi và
giá trị vi.
v Hãy chọn ra các món có thể bỏ vào ba lô có
trọng lượng tối đa là W sao cho tổng các giá trị
các món đồ là lớn nhất.
43 9/17/16 Trần Minh Thái - Phạm Đức Thành
Cách giải
v Gọi F[i, j] là giá trị lớn nhất có thể có bằng
cách chọn trong các món {1,2,..,j} với giới hạn
trọng lượng j
v Như vậy F[n, W] chính là giá trị lớn nhất khi
được chọn trong số n gói với giới hạn trọng
lượng W
44 9/17/16 Trần Minh Thái - Phạm Đức Thành
B1: Công thức truy hồi tính F[i, j]
v Với giới hạn trọng lượng j, việc chọn phương án
tối ưu trong số các gói {1, 2, .., i-1, i}, để có giá
trị lớn nhất có 2 khả năng:
Ø Không chọn gói thứ i: F[i, j] = F[i-1, j].
Ø Chọn gói thứ i (wi<=j): F[i, j]=vi + F[i-1, j – wi].
Chọn F[i, j] là giá trị lớn nhất trong hai giá trị thu
được ở trên.
v Cơ sở quy hoạch động:
F[0, j] = 0 với mọi j
45 9/17/16 Trần Minh Thái - Phạm Đức Thành
v B2:
Lập
bảng
phương án:
...
F 0 1 2
0
1
2
... ... ... ...
n
... W
...
...
...
...
...
ộ
v B ng F: n+1 dòng, W+1 c t
ộ ằ
ơ ở
ạ
ộ
ầ
ứ
ứ
ế
ả
v Dòng đ u tiên: c s quy ho ch đ ng, toàn b b ng 0
ồ
ứ
v Dòng th hai đ n dòng th n: dùng công th c truy h i
46 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng đầu tiên:
9
0
10 11
0
0
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1
2
3
4
5
47 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=1:
9
0
3
10 11
0
0
3
3
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 3 3 3 3 3 3
2
3
4
5
48 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=2:
9
0
3
7
10 11
0
0
3
3
7
7
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 3 3 3 3 3 3
2 0 0 0 3 4 4 4 7 7
3
4
5
49 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=3:
9
0
3
7
8
10 11
0
0
3
3
7
7
8
8
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 3 3 3 3 3 3
2 0 0 0 3 4 4 4 7 7
3 0 0 0 3 4 4 4 7 7
4
5
50 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=4:
9
0
3
7
8
F 0 1 2 3 4 5 6 7 8
10 11
0 0 0 0 0 0 0 0 0 0
0
0
1 0 0 0 3 3 3 3 3 3
3
3
2 0 0 0 3 4 4 4 7 7
7
7
3 0 0 0 3 4 4 4 7 7
8
8
4 0 0 0 3 4 4 4 7 7 10 10 10
5
51 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=5:
9
0
3
7
8
F 0 1 2 3 4 5 6 7 8
10 11
0 0 0 0 0 0 0 0 0 0
0
0
1 0 0 0 3 3 3 3 3 3
3
3
2 0 0 0 3 4 4 4 7 7
7
7
3 0 0 0 3 4 4 4 7 7
8
8
4 0 0 0 3 4 4 4 7 7 10 10 10
5 0 0 0 3 4 4 4 7 8 10 10 11
52 9/17/16 Trần Minh Thái - Phạm Đức Thành
B3: Truy vết
v Từ F[n, W]:
Ø Nếu F[n,W]=F[n-1, W] thì không chọn gói
n. Xét tiếp F[n-1, W].
Ø Ngược lại (F[n, W] ≠ F[n-1, W]) thì chọn gói
thứ n. Xét tiếp F[n-1, W-wn].
v Lặp lại cho đến dòng đầu tiên của bảng
phương án.
53 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Tập tin BALO.INP:
Ø Dòng 1: số n và
BALO.INP BALO.OUT
11
5 11
1
W.
5 2 1
2
3 3
3
4 4
Ø n dòng tiếp theo:
dòng thứ i chứa 2
số wi, vi.
v Tập tin BALO.OUT:
4
5 4
5
9 10
Ø Dòng 1: Giá trị lớn
nhất có thể bỏ
vào ba lô.
6
4 4
Ø Dòng 2: chỉ số đồ
vật được lấy bỏ
vào ba lô.
54 9/17/16 Trần Minh Thái - Phạm Đức Thành
55 Trần Minh Thái - Phạm Đức Thành
static bool docFile(ref int[] w, ref int[]v, ref int n, ref int W,
string fileName)
{ StreamReader sr = new StreamReader(fileName);
string S = sr.ReadLine();
string[] M = S.Split(new Char[] { ' ' }); int j = 0;
while (M[j] == "") j++; n = int.Parse(M[j++]);
while (M[j] == "") j++; W = int.Parse(M[j++]);
w = new int[n + 1]; v = new int[n + 1];
for (int i = 0; i < n; i++)
{ S = sr.ReadLine(); M = S.Split(new Char[] { ' ' }); j =
0;
while (M[j] == "") j++; w[i] = int.Parse(M[j++]);
while (M[j] == "") j++; v[i] = int.Parse(M[j++]);
}
return true;
} 9/17/16
56
static void bangPhuongAn(int[] w, int[] v, int n, int W, out
int[,] F)
{
F = new int[n + 1, W + 1];
for (int j = 0; j <= W; j++)
F[0, j] = 0;
for(int i=1; i<= n; i++)
for(int j=0; j<= W; j++)
{
F[i, j] = F[i - 1, j];
if (j >= w[i - 1] && F[i, j] < F[i - 1, j - w[i - 1]] + v[i -
1])
F[i, j] = F[i - 1, j - w[i - 1]] + v[i - 1];
}
} 9/17/16
Trần Minh Thái - Phạm Đức Thành
static bool truyVet (int[]w, int[]v, int n, int W, int[,]F, string
fName)
{
StreamWriter sw = new StreamWriter(fName);
57
sw.WriteLine("{0}", F[n,W]);
while (n>0)
{ if (F[n, W] != F[n - 1, W])
{ sw.Write("{0,4}", n);
W = W - w[n-1];
}
n--;
}
sw.Close();
return true;
} 9/17/16
Trần Minh Thái - Phạm Đức Thành
static void Main(string[] args)
{
int[] w=null, v=null; int n=0, W=0; int[,] F;
if (docFile(ref w,ref v,ref n,ref W,"..//..//BALO.INP")
==true)
{
bangPhuongAn(w, v, n, W, out F);
if (truyVet (w,v,n,W,F,"..//..//BALO.OUT") == true)
Console.WriteLine("Luu file thanh cong");
}
Console.ReadLine();
}
58 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Phương pháp quy hoạch động do nhà toán
học Richard Bellman phát minh vào năm
1953.
v Ý tưởng của nguyên lý tối ưu Bellman là:
Ø “Với mỗi quá trình điều khiển tối ưu, đối
với trạng thái bắt đầu A0, với trạng thái A
trong quá trình đó, phần quá trình kể từ
trạng thái A xem như trạng thái bắt đầu
cũng là tối ưu”.
59 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Phương pháp quy hoạch động thường được
dùng để giải các bài toán tối ưu có bản chất
là đệ quy:
Ø Việc tìm phương án tối ưu có thể đưa về
tìm tối ưu cho các bài toán con hữu hạn.
Ø Thuật toán đệ quy đã tìm hiểu ở chương 3
đa số là dùng nguyên lý “chia để trị” và
trong quy hoạch động cũng áp dụng
nguyên lý này.
60 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Có 2 loại quy hoạch động:
Ø Phép phân giải đệ quy theo hướng “từ trên
xuống” (top-down).
Ø Phép phân giải đệ quy theo hướng “từ
dưới lên” (bottom-up).
61 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Ta có một số khái niệm sau:
Ø Bài toán quy hoạch động: giải theo
phương pháp quy hoạch động.
Ø Công thức truy hồi của quy hoạch động: là
công thức phối hợp nghiệm của các bài
toán con để có nghiệm cho bài toán lớn.
Ø Bảng phương án của quy hoạch động: là
không gian lưu trữ lời giải của các bài toán
con để tìm cách phối hợp chúng.
62 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Muốn giải bằng phương pháp quy hoạch
động, bài toán cần thỏa mãn các yêu cầu
sau:
Ø Phải phân rã được bài toán lớn thành các
bài toán con và sự phối hợp lời giải đó cho
ta lời giải cuối cùng của bài toán lớn.
Ø Phải có đủ không gian bộ nhớ vật lý.
Ø Quá trình phối hợp lời giải bài toán con
đến bài toán ban đầu, phải có một số bước
hữu hạn (tính dừng của chương trình).
63 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Các bước cài đặt:
Ø Bước 1: Phân tích bài toán, lập công thức
truy hồi.
Ø Bước 2: Giải tất cả các bài toán con và lưu
vào bảng phương án (dùng mảng một chiều
hoặc hai chiều).
Ø Bước 3: Dùng công thức truy hồi để phối
hợp các lời giải của những bài toán con, lặp
cho đến khi tìm được lời giải ban đầu.
Ø Bước 4: Dựa vào bảng phương án, truy vết
tìm lời giải tối ưu.
64 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Cũng gần giống như phần đệ quy ở chương 3:
khi phân tích bài toán và tìm ra công thức truy
hồi, ta sẽ phải tìm ra hai thành phần sau:
Ø Phần cơ sở quy hoạch động (giống như phần
cố định – neo trong chương 3 về đệ quy).
Ø Phần truy hồi (công thức truy hồi – giống
như phần đệ quy của chương 3).
65 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập
Bài 1: Bài toán bố trí phòng họp
v Có n cuộc họp, cuộc họp thứ i bắt đầu vào thời
điểm si và kết thúc fi.
v Do chỉ có một phòng hội thảo nên hai cuộc họp
bất kỳ sẽ được cùng bố trí phục vụ nếu khoảng
thời gian làm việc của các cuộc họp này chỉ
giao nhau tại các đầu mút.
v Hãy bố trí lịch họp sao cho phục vụ được nhiều
cuộc họp nhất.
66 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập
Bài 2: Bài toán điền dấu biểu thức
v Cho n số tự nhiên a1, a2, .., an. Ban đầu các số
được đặt liên tiếp theo đúng thứ tự cách nhau
bởi dấu chấm hỏi (?) như sau: a1 ? a2 ? .. ? ,
an.
v Cho trước số nguyên S, có cách nào thay các
dấu chấm hỏi bằng dấu công (+) hoặc trừ (-) để
được một biểu thức số học cho giá trị là S
không?
v Ví dụ: dãy ban đầu 1 ? 2? 3 ? 4 với K=0, thì cho
kết quả 1-2-3+4 = 0.
67 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập
Bài 3: Bài toán xâu con chung dài nhất.
v Xâu ký tự S gọi là xâu con của xâu M nếu có thể
xóa bớt một số ký tự trong xâu M để được xâu
S.
v Nhập vào hai xâu ký tự X, Y và tìm xâu Z có độ
dài lớn là xâu con của cả X và Y.
v Ví dụ: nhập X= “abcdefghi123” và Y=
“abc1def2ghi3” thì Z là “abcdefghi3”.
68 9/17/16 Trần Minh Thái - Phạm Đức Thành
35 9/17/16 Trần Minh Thái - Phạm Đức Thành
B2: Lập bảng phương án: v Tạo thêm dãy phụ T để lưu vị trí kế tiếp của của A[i] trong dãy con đơn điệu dài nhất: T[i]=jmax, với A[jmax] là phần tử kế tiếp của A[i].
v Ta có bảng phương án sau:
0
1
2
3
4
5
6
7
8
9
10
i
A[i]
(cid:0)
5
2
3
4
9
10
5
6
7
8
11 +(cid:0)
L[i]
9
5
8
7
6
3
2
5
4
3
2
1
2
8
3
4
7
6
11
8
9
10
11
T[i]
36 9/17/16 Trần Minh Thái - Phạm Đức Thành
B3: Truy vết: v Sau khi tính đồng hành hai dãy L và T, ta sẽ bắt
đầu từ T[0] và có kết quả như sau: T[T[T[0]]] (cid:0)
T[T[0]] (cid:0)
T[0] (cid:0)
...
v Thuật toán truy vết như sau:
T[0]
i (cid:0) while i ≠ n+1 do {
write A[i]; i (cid:0) T[i];
}
37 9/17/16 Trần Minh Thái - Phạm Đức Thành
Ví dụ
DATA.INP
DAYCONTANG.OUT
1
10
7
2
5 2 3 4 9 10 5 6 7 8
2 3 4 5 6 7 8
v Tập tin DATA.INP:
Ø Dòng 1: Số phần tử của dãy n=10. Ø Dòng 2: n (10) số cách nhau bởi khoảng
trắng.
v Tập tin DAYCONTANG.OUT:
Ø Dòng 1: Độ dài dãy con tăng. Ø Dòng 2: các phần tử trong dãy con tăng.
38 9/17/16 Trần Minh Thái - Phạm Đức Thành
static bool docFile(ref int[]A,string fileName) { StreamReader sr = new StreamReader(fileName); if( sr == null) { Console.WriteLine("Loi khi doc file"); return false; } int n = int.Parse(sr.ReadLine()); A = new int[n + 2]; string S = sr.ReadLine(); string[] M = S.Split(new Char[] { ' ' }); int j = 0; for (int i = 1; i <= n; i++) { while (M[j] == "") j++; A[i] = int.Parse(M[j++]); } return true; }
39 9/17/16 Trần Minh Thái - Phạm Đức Thành
0
(cid:0)
11 +(cid:0) 1
6 10 2 11
4 4 6 7
1 5 5 8
3 3 7 4
5 9 3 6
9 2
7 5 5 8
i A[i] L[i] T[i]
2 2 8 3 taoBangPhuongAn(int[]A,out
8 6 4 9 int
10 9 8 7 2 3 11 10 []L,out
static void int[]T) { int n = A.Length; L = new int[n]; T = new int[n]; A[0] = int.MinValue;
A[n - 1] = int.MaxValue;
40 Trần Minh Thái - Phạm Đức Thành
L[n - 1] = 1; for(int i= n-2; i>=0; i--) { int jmax = n - 1; for (int j = i + 1; j <= n - 1; j++) if (A[j] > A[i] && L[j] > L[jmax]) jmax = j; L[i] = L[jmax] + 1; T[i] = jmax; } }9/17/16
0
(cid:0)
11 +(cid:0) 1
9 2
1 5 5 8
2 2 8 3
3 3 7 4
4 4 6 7
5 9 3 6
6 10 2 11
7 5 5 8
8 6 4 9
9 7 3 10
10 8 2 11
i A[i] L[i] T[i]
static bool truyVet (int[] A, int[] L, int[] T, string fileName) {
StreamWriter sw = new StreamWriter(fileName);
41 Trần Minh Thái - Phạm Đức Thành
if(sw==null)
{Console.WriteLine("Khong ghi duoc file");return
false; }
sw.WriteLine("{0}", L[0] - 2); int i = T[0];
while(i
static void Main(string[] args)
{
int[] A = null, L, T;
if(docFile(ref A,"DATA.INP")==true)
{
taoBangPhuongAn(A, out L, out T);
if (truyVet (A, L, T, "DAYCONTANG.OUT") ==
true)
Console.WriteLine("Luu file thanh cong")
}
}
42 9/17/16 Trần Minh Thái - Phạm Đức Thành
Bài toán chiếc ba lô dạng một
Mô tả:
v Có n món đồ, vật thứ i có trọng lượng là wi và
giá trị vi.
v Hãy chọn ra các món có thể bỏ vào ba lô có
trọng lượng tối đa là W sao cho tổng các giá trị
các món đồ là lớn nhất.
43 9/17/16 Trần Minh Thái - Phạm Đức Thành
Cách giải
v Gọi F[i, j] là giá trị lớn nhất có thể có bằng
cách chọn trong các món {1,2,..,j} với giới hạn
trọng lượng j
v Như vậy F[n, W] chính là giá trị lớn nhất khi
được chọn trong số n gói với giới hạn trọng
lượng W
44 9/17/16 Trần Minh Thái - Phạm Đức Thành
B1: Công thức truy hồi tính F[i, j]
v Với giới hạn trọng lượng j, việc chọn phương án
tối ưu trong số các gói {1, 2, .., i-1, i}, để có giá
trị lớn nhất có 2 khả năng:
Ø Không chọn gói thứ i: F[i, j] = F[i-1, j].
Ø Chọn gói thứ i (wi<=j): F[i, j]=vi + F[i-1, j – wi].
Chọn F[i, j] là giá trị lớn nhất trong hai giá trị thu
được ở trên.
v Cơ sở quy hoạch động:
F[0, j] = 0 với mọi j
45 9/17/16 Trần Minh Thái - Phạm Đức Thành
v B2:
Lập
bảng
phương án:
...
F 0 1 2
0
1
2
... ... ... ...
n
... W
...
...
...
...
...
ộ
v B ng F: n+1 dòng, W+1 c t
ộ ằ
ơ ở
ạ
ộ
ầ
ứ
ứ
ế
ả
v Dòng đ u tiên: c s quy ho ch đ ng, toàn b b ng 0
ồ
ứ
v Dòng th hai đ n dòng th n: dùng công th c truy h i
46 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng đầu tiên:
9
0
10 11
0
0
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1
2
3
4
5
47 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=1:
9
0
3
10 11
0
0
3
3
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 3 3 3 3 3 3
2
3
4
5
48 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=2:
9
0
3
7
10 11
0
0
3
3
7
7
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 3 3 3 3 3 3
2 0 0 0 3 4 4 4 7 7
3
4
5
49 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=3:
9
0
3
7
8
10 11
0
0
3
3
7
7
8
8
F 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 3 3 3 3 3 3
2 0 0 0 3 4 4 4 7 7
3 0 0 0 3 4 4 4 7 7
4
5
50 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=4:
9
0
3
7
8
F 0 1 2 3 4 5 6 7 8
10 11
0 0 0 0 0 0 0 0 0 0
0
0
1 0 0 0 3 3 3 3 3 3
3
3
2 0 0 0 3 4 4 4 7 7
7
7
3 0 0 0 3 4 4 4 7 7
8
8
4 0 0 0 3 4 4 4 7 7 10 10 10
5
51 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4}
v Dòng thứ i=5:
9
0
3
7
8
F 0 1 2 3 4 5 6 7 8
10 11
0 0 0 0 0 0 0 0 0 0
0
0
1 0 0 0 3 3 3 3 3 3
3
3
2 0 0 0 3 4 4 4 7 7
7
7
3 0 0 0 3 4 4 4 7 7
8
8
4 0 0 0 3 4 4 4 7 7 10 10 10
5 0 0 0 3 4 4 4 7 8 10 10 11
52 9/17/16 Trần Minh Thái - Phạm Đức Thành
B3: Truy vết
v Từ F[n, W]:
Ø Nếu F[n,W]=F[n-1, W] thì không chọn gói
n. Xét tiếp F[n-1, W].
Ø Ngược lại (F[n, W] ≠ F[n-1, W]) thì chọn gói
thứ n. Xét tiếp F[n-1, W-wn].
v Lặp lại cho đến dòng đầu tiên của bảng
phương án.
53 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Tập tin BALO.INP:
Ø Dòng 1: số n và
BALO.INP BALO.OUT
11
5 11
1
W.
5 2 1
2
3 3
3
4 4
Ø n dòng tiếp theo:
dòng thứ i chứa 2
số wi, vi.
v Tập tin BALO.OUT:
4
5 4
5
9 10
Ø Dòng 1: Giá trị lớn
nhất có thể bỏ
vào ba lô.
6
4 4
Ø Dòng 2: chỉ số đồ
vật được lấy bỏ
vào ba lô.
54 9/17/16 Trần Minh Thái - Phạm Đức Thành
55 Trần Minh Thái - Phạm Đức Thành
static bool docFile(ref int[] w, ref int[]v, ref int n, ref int W,
string fileName)
{ StreamReader sr = new StreamReader(fileName);
string S = sr.ReadLine();
string[] M = S.Split(new Char[] { ' ' }); int j = 0;
while (M[j] == "") j++; n = int.Parse(M[j++]);
while (M[j] == "") j++; W = int.Parse(M[j++]);
w = new int[n + 1]; v = new int[n + 1];
for (int i = 0; i < n; i++)
{ S = sr.ReadLine(); M = S.Split(new Char[] { ' ' }); j =
0;
while (M[j] == "") j++; w[i] = int.Parse(M[j++]);
while (M[j] == "") j++; v[i] = int.Parse(M[j++]);
}
return true;
} 9/17/16
56
static void bangPhuongAn(int[] w, int[] v, int n, int W, out
int[,] F)
{
F = new int[n + 1, W + 1];
for (int j = 0; j <= W; j++)
F[0, j] = 0;
for(int i=1; i<= n; i++)
for(int j=0; j<= W; j++)
{
F[i, j] = F[i - 1, j];
if (j >= w[i - 1] && F[i, j] < F[i - 1, j - w[i - 1]] + v[i -
1])
F[i, j] = F[i - 1, j - w[i - 1]] + v[i - 1];
}
} 9/17/16
Trần Minh Thái - Phạm Đức Thành
static bool truyVet (int[]w, int[]v, int n, int W, int[,]F, string
fName)
{
StreamWriter sw = new StreamWriter(fName);
57
sw.WriteLine("{0}", F[n,W]);
while (n>0)
{ if (F[n, W] != F[n - 1, W])
{ sw.Write("{0,4}", n);
W = W - w[n-1];
}
n--;
}
sw.Close();
return true;
} 9/17/16
Trần Minh Thái - Phạm Đức Thành
static void Main(string[] args)
{
int[] w=null, v=null; int n=0, W=0; int[,] F;
if (docFile(ref w,ref v,ref n,ref W,"..//..//BALO.INP")
==true)
{
bangPhuongAn(w, v, n, W, out F);
if (truyVet (w,v,n,W,F,"..//..//BALO.OUT") == true)
Console.WriteLine("Luu file thanh cong");
}
Console.ReadLine();
}
58 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Phương pháp quy hoạch động do nhà toán
học Richard Bellman phát minh vào năm
1953.
v Ý tưởng của nguyên lý tối ưu Bellman là:
Ø “Với mỗi quá trình điều khiển tối ưu, đối
với trạng thái bắt đầu A0, với trạng thái A
trong quá trình đó, phần quá trình kể từ
trạng thái A xem như trạng thái bắt đầu
cũng là tối ưu”.
59 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Phương pháp quy hoạch động thường được
dùng để giải các bài toán tối ưu có bản chất
là đệ quy:
Ø Việc tìm phương án tối ưu có thể đưa về
tìm tối ưu cho các bài toán con hữu hạn.
Ø Thuật toán đệ quy đã tìm hiểu ở chương 3
đa số là dùng nguyên lý “chia để trị” và
trong quy hoạch động cũng áp dụng
nguyên lý này.
60 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Có 2 loại quy hoạch động:
Ø Phép phân giải đệ quy theo hướng “từ trên
xuống” (top-down).
Ø Phép phân giải đệ quy theo hướng “từ
dưới lên” (bottom-up).
61 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Ta có một số khái niệm sau:
Ø Bài toán quy hoạch động: giải theo
phương pháp quy hoạch động.
Ø Công thức truy hồi của quy hoạch động: là
công thức phối hợp nghiệm của các bài
toán con để có nghiệm cho bài toán lớn.
Ø Bảng phương án của quy hoạch động: là
không gian lưu trữ lời giải của các bài toán
con để tìm cách phối hợp chúng.
62 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Muốn giải bằng phương pháp quy hoạch
động, bài toán cần thỏa mãn các yêu cầu
sau:
Ø Phải phân rã được bài toán lớn thành các
bài toán con và sự phối hợp lời giải đó cho
ta lời giải cuối cùng của bài toán lớn.
Ø Phải có đủ không gian bộ nhớ vật lý.
Ø Quá trình phối hợp lời giải bài toán con
đến bài toán ban đầu, phải có một số bước
hữu hạn (tính dừng của chương trình).
63 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Các bước cài đặt:
Ø Bước 1: Phân tích bài toán, lập công thức
truy hồi.
Ø Bước 2: Giải tất cả các bài toán con và lưu
vào bảng phương án (dùng mảng một chiều
hoặc hai chiều).
Ø Bước 3: Dùng công thức truy hồi để phối
hợp các lời giải của những bài toán con, lặp
cho đến khi tìm được lời giải ban đầu.
Ø Bước 4: Dựa vào bảng phương án, truy vết
tìm lời giải tối ưu.
64 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Cũng gần giống như phần đệ quy ở chương 3:
khi phân tích bài toán và tìm ra công thức truy
hồi, ta sẽ phải tìm ra hai thành phần sau:
Ø Phần cơ sở quy hoạch động (giống như phần
cố định – neo trong chương 3 về đệ quy).
Ø Phần truy hồi (công thức truy hồi – giống
như phần đệ quy của chương 3).
65 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập
Bài 1: Bài toán bố trí phòng họp
v Có n cuộc họp, cuộc họp thứ i bắt đầu vào thời
điểm si và kết thúc fi.
v Do chỉ có một phòng hội thảo nên hai cuộc họp
bất kỳ sẽ được cùng bố trí phục vụ nếu khoảng
thời gian làm việc của các cuộc họp này chỉ
giao nhau tại các đầu mút.
v Hãy bố trí lịch họp sao cho phục vụ được nhiều
cuộc họp nhất.
66 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập
Bài 2: Bài toán điền dấu biểu thức
v Cho n số tự nhiên a1, a2, .., an. Ban đầu các số
được đặt liên tiếp theo đúng thứ tự cách nhau
bởi dấu chấm hỏi (?) như sau: a1 ? a2 ? .. ? ,
an.
v Cho trước số nguyên S, có cách nào thay các
dấu chấm hỏi bằng dấu công (+) hoặc trừ (-) để
được một biểu thức số học cho giá trị là S
không?
v Ví dụ: dãy ban đầu 1 ? 2? 3 ? 4 với K=0, thì cho
kết quả 1-2-3+4 = 0.
67 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập
Bài 3: Bài toán xâu con chung dài nhất.
v Xâu ký tự S gọi là xâu con của xâu M nếu có thể
xóa bớt một số ký tự trong xâu M để được xâu
S.
v Nhập vào hai xâu ký tự X, Y và tìm xâu Z có độ
dài lớn là xâu con của cả X và Y.
v Ví dụ: nhập X= “abcdefghi123” và Y=
“abc1def2ghi3” thì Z là “abcdefghi3”.
68 9/17/16 Trần Minh Thái - Phạm Đức Thành
static void Main(string[] args) { int[] A = null, L, T; if(docFile(ref A,"DATA.INP")==true) { taoBangPhuongAn(A, out L, out T); if (truyVet (A, L, T, "DAYCONTANG.OUT") == true) Console.WriteLine("Luu file thanh cong") } }
42 9/17/16 Trần Minh Thái - Phạm Đức Thành
Bài toán chiếc ba lô dạng một
Mô tả: v Có n món đồ, vật thứ i có trọng lượng là wi và
giá trị vi.
v Hãy chọn ra các món có thể bỏ vào ba lô có trọng lượng tối đa là W sao cho tổng các giá trị các món đồ là lớn nhất.
43 9/17/16 Trần Minh Thái - Phạm Đức Thành
Cách giải
v Gọi F[i, j] là giá trị lớn nhất có thể có bằng cách chọn trong các món {1,2,..,j} với giới hạn trọng lượng j
v Như vậy F[n, W] chính là giá trị lớn nhất khi được chọn trong số n gói với giới hạn trọng lượng W
44 9/17/16 Trần Minh Thái - Phạm Đức Thành
B1: Công thức truy hồi tính F[i, j] v Với giới hạn trọng lượng j, việc chọn phương án tối ưu trong số các gói {1, 2, .., i-1, i}, để có giá trị lớn nhất có 2 khả năng: Ø Không chọn gói thứ i: F[i, j] = F[i-1, j]. Ø Chọn gói thứ i (wi<=j): F[i, j]=vi + F[i-1, j – wi]. Chọn F[i, j] là giá trị lớn nhất trong hai giá trị thu được ở trên. v Cơ sở quy hoạch động:
F[0, j] = 0 với mọi j
45 9/17/16 Trần Minh Thái - Phạm Đức Thành
v B2:
Lập
bảng phương án:
...
F 0 1 2 0 1 2 ... ... ... ... n
... W ... ... ... ... ...
ộ v B ng F: n+1 dòng, W+1 c t
ộ ằ
ơ ở
ạ
ộ
ầ ứ
ứ
ế
ả v Dòng đ u tiên: c s quy ho ch đ ng, toàn b b ng 0 ồ ứ v Dòng th hai đ n dòng th n: dùng công th c truy h i
46 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4} v Dòng đầu tiên:
9 0
10 11 0 0
F 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5
47 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4} v Dòng thứ i=1:
9 0 3
10 11 0 0 3 3
F 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 3 3 3 3 3 2 3 4 5
48 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4} v Dòng thứ i=2:
9 0 3 7
10 11 0 0 3 3 7 7
F 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 3 3 3 3 3 2 0 0 0 3 4 4 4 7 7 3 4 5
49 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4} v Dòng thứ i=3:
9 0 3 7 8
10 11 0 0 3 3 7 7 8 8
F 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 3 3 3 3 3 2 0 0 0 3 4 4 4 7 7 3 0 0 0 3 4 4 4 7 7 4 5
50 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4} v Dòng thứ i=4:
9 0 3 7 8
F 0 1 2 3 4 5 6 7 8 10 11 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 3 3 3 3 3 3 3 2 0 0 0 3 4 4 4 7 7 7 7 3 0 0 0 3 4 4 4 7 7 8 8 4 0 0 0 3 4 4 4 7 7 10 10 10 5
51 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Ví dụ: n=5, W=11, w={3,4,5,9,4} và v={3,4,4,10,4} v Dòng thứ i=5:
9 0 3 7 8
F 0 1 2 3 4 5 6 7 8 10 11 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 3 3 3 3 3 3 3 2 0 0 0 3 4 4 4 7 7 7 7 3 0 0 0 3 4 4 4 7 7 8 8 4 0 0 0 3 4 4 4 7 7 10 10 10 5 0 0 0 3 4 4 4 7 8 10 10 11
52 9/17/16 Trần Minh Thái - Phạm Đức Thành
B3: Truy vết v Từ F[n, W]:
Ø Nếu F[n,W]=F[n-1, W] thì không chọn gói
n. Xét tiếp F[n-1, W].
Ø Ngược lại (F[n, W] ≠ F[n-1, W]) thì chọn gói
thứ n. Xét tiếp F[n-1, W-wn].
v Lặp lại cho đến dòng đầu tiên của bảng
phương án.
53 9/17/16 Trần Minh Thái - Phạm Đức Thành
v Tập tin BALO.INP:
Ø Dòng 1: số n và
BALO.INP BALO.OUT 11 5 11
1
W.
5 2 1
2
3 3
3
4 4
Ø n dòng tiếp theo: dòng thứ i chứa 2 số wi, vi.
v Tập tin BALO.OUT:
4
5 4
5
9 10
Ø Dòng 1: Giá trị lớn nhất có thể bỏ vào ba lô.
6
4 4
Ø Dòng 2: chỉ số đồ vật được lấy bỏ vào ba lô.
54 9/17/16 Trần Minh Thái - Phạm Đức Thành
55 Trần Minh Thái - Phạm Đức Thành
static bool docFile(ref int[] w, ref int[]v, ref int n, ref int W, string fileName) { StreamReader sr = new StreamReader(fileName); string S = sr.ReadLine(); string[] M = S.Split(new Char[] { ' ' }); int j = 0; while (M[j] == "") j++; n = int.Parse(M[j++]); while (M[j] == "") j++; W = int.Parse(M[j++]); w = new int[n + 1]; v = new int[n + 1]; for (int i = 0; i < n; i++) { S = sr.ReadLine(); M = S.Split(new Char[] { ' ' }); j = 0; while (M[j] == "") j++; w[i] = int.Parse(M[j++]); while (M[j] == "") j++; v[i] = int.Parse(M[j++]); } return true; } 9/17/16
56
static void bangPhuongAn(int[] w, int[] v, int n, int W, out int[,] F) { F = new int[n + 1, W + 1]; for (int j = 0; j <= W; j++) F[0, j] = 0; for(int i=1; i<= n; i++) for(int j=0; j<= W; j++) { F[i, j] = F[i - 1, j]; if (j >= w[i - 1] && F[i, j] < F[i - 1, j - w[i - 1]] + v[i - 1]) F[i, j] = F[i - 1, j - w[i - 1]] + v[i - 1]; } } 9/17/16
Trần Minh Thái - Phạm Đức Thành
static bool truyVet (int[]w, int[]v, int n, int W, int[,]F, string fName) {
StreamWriter sw = new StreamWriter(fName);
57
sw.WriteLine("{0}", F[n,W]); while (n>0) { if (F[n, W] != F[n - 1, W]) { sw.Write("{0,4}", n); W = W - w[n-1]; } n--; } sw.Close(); return true; } 9/17/16
Trần Minh Thái - Phạm Đức Thành
static void Main(string[] args) { int[] w=null, v=null; int n=0, W=0; int[,] F; if (docFile(ref w,ref v,ref n,ref W,"..//..//BALO.INP") ==true) { bangPhuongAn(w, v, n, W, out F); if (truyVet (w,v,n,W,F,"..//..//BALO.OUT") == true) Console.WriteLine("Luu file thanh cong"); } Console.ReadLine(); }
58 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương v Phương pháp quy hoạch động do nhà toán học Richard Bellman phát minh vào năm 1953.
v Ý tưởng của nguyên lý tối ưu Bellman là:
Ø “Với mỗi quá trình điều khiển tối ưu, đối với trạng thái bắt đầu A0, với trạng thái A trong quá trình đó, phần quá trình kể từ trạng thái A xem như trạng thái bắt đầu cũng là tối ưu”.
59 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương v Phương pháp quy hoạch động thường được dùng để giải các bài toán tối ưu có bản chất là đệ quy: Ø Việc tìm phương án tối ưu có thể đưa về tìm tối ưu cho các bài toán con hữu hạn. Ø Thuật toán đệ quy đã tìm hiểu ở chương 3 đa số là dùng nguyên lý “chia để trị” và trong quy hoạch động cũng áp dụng nguyên lý này.
60 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Có 2 loại quy hoạch động:
Ø Phép phân giải đệ quy theo hướng “từ trên
xuống” (top-down).
Ø Phép phân giải đệ quy theo hướng “từ
dưới lên” (bottom-up).
61 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Ta có một số khái niệm sau:
Ø Bài toán quy hoạch động: giải theo
phương pháp quy hoạch động.
Ø Công thức truy hồi của quy hoạch động: là công thức phối hợp nghiệm của các bài toán con để có nghiệm cho bài toán lớn. Ø Bảng phương án của quy hoạch động: là không gian lưu trữ lời giải của các bài toán con để tìm cách phối hợp chúng.
62 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương v Muốn giải bằng phương pháp quy hoạch động, bài toán cần thỏa mãn các yêu cầu sau: Ø Phải phân rã được bài toán lớn thành các bài toán con và sự phối hợp lời giải đó cho ta lời giải cuối cùng của bài toán lớn. Ø Phải có đủ không gian bộ nhớ vật lý. Ø Quá trình phối hợp lời giải bài toán con đến bài toán ban đầu, phải có một số bước hữu hạn (tính dừng của chương trình).
63 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương
v Các bước cài đặt:
Ø Bước 1: Phân tích bài toán, lập công thức
truy hồi.
Ø Bước 2: Giải tất cả các bài toán con và lưu vào bảng phương án (dùng mảng một chiều hoặc hai chiều).
Ø Bước 3: Dùng công thức truy hồi để phối hợp các lời giải của những bài toán con, lặp cho đến khi tìm được lời giải ban đầu.
Ø Bước 4: Dựa vào bảng phương án, truy vết
tìm lời giải tối ưu.
64 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.4] Tóm tắt chương v Cũng gần giống như phần đệ quy ở chương 3: khi phân tích bài toán và tìm ra công thức truy hồi, ta sẽ phải tìm ra hai thành phần sau: Ø Phần cơ sở quy hoạch động (giống như phần
cố định – neo trong chương 3 về đệ quy).
Ø Phần truy hồi (công thức truy hồi – giống
như phần đệ quy của chương 3).
65 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập
Bài 1: Bài toán bố trí phòng họp v Có n cuộc họp, cuộc họp thứ i bắt đầu vào thời
điểm si và kết thúc fi.
v Do chỉ có một phòng hội thảo nên hai cuộc họp bất kỳ sẽ được cùng bố trí phục vụ nếu khoảng thời gian làm việc của các cuộc họp này chỉ giao nhau tại các đầu mút.
v Hãy bố trí lịch họp sao cho phục vụ được nhiều
cuộc họp nhất.
66 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập Bài 2: Bài toán điền dấu biểu thức v Cho n số tự nhiên a1, a2, .., an. Ban đầu các số được đặt liên tiếp theo đúng thứ tự cách nhau bởi dấu chấm hỏi (?) như sau: a1 ? a2 ? .. ? , an.
v Cho trước số nguyên S, có cách nào thay các dấu chấm hỏi bằng dấu công (+) hoặc trừ (-) để được một biểu thức số học cho giá trị là S không?
v Ví dụ: dãy ban đầu 1 ? 2? 3 ? 4 với K=0, thì cho
kết quả 1-2-3+4 = 0.
67 9/17/16 Trần Minh Thái - Phạm Đức Thành
[4.5] Bài tập
Bài 3: Bài toán xâu con chung dài nhất. v Xâu ký tự S gọi là xâu con của xâu M nếu có thể xóa bớt một số ký tự trong xâu M để được xâu S.
v Nhập vào hai xâu ký tự X, Y và tìm xâu Z có độ
dài lớn là xâu con của cả X và Y.
v Ví dụ: nhập X= “abcdefghi123” và Y=
“abc1def2ghi3” thì Z là “abcdefghi3”.
68 9/17/16 Trần Minh Thái - Phạm Đức Thành
