Bài giảng Cấu trúc dữ liệu và thuật giải - Tạ Thúc Nhu

 && F[i, v] <= F[i-1, (v - r + k)%k])
F[i, v] = F[ i -1, (v - r + k)%k] + 1;
}
}
17
33
Truy vết
Bắt đầu từ ô F[n, 0] trên dòng n ta dò ngược về dòng 0 theo nguyên tắc:
• Nếu F[i–1, (v-r+k)%k] > 0 và F[i, v] > F[i–1, (v-r+k)%k]: 
– A[i] được chọn
– Truy tiếp ô F[i -1, (v-r+k)%k].
• Ngược lại thì A[i] không được chọn, ta truy tiếp ô F[i -1, v].
6
5
4
3
2
1
i
2 | 61 | 54 | 53 | 42 | 43
4 | 43 | 32 | 31 | 40 | 40
2 | 31 | 20 | 24 | 33 | 32
2 | 31 | 20 | 24 | 13 | 02
3 | 02 | 01 | 20 | 1 4 | 01
000101
43210r=A[i] v
34
Tìm dãy con không giảm dài nhất
Cho một dãy gồm n số nguyên. Hãy loại bỏ khỏi dãy một số phần 
tử để được một dãy con không giảm dài nhất. In ra dãy con đó.
Ví dụ: với n = 10 và dãy A được cho trong bảng.
Hãy chỉ ra dãy con không giảm dài nhất ?
4155-3185-762Dãy A
10987654321I
18
35
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:
3432232121Cách 2
4433332221Cách 1
4155-3185-762Dãy A
10987654321I
36
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
3432232121L(i)
4155-3185-762Dãy A[i]
10987654321I
19
37
Xây dựng bảng phương án:
– Mảng L[1..n]: L[i] chứa giá trị của L(i)
– Mảng Truoc[1..n]: Truoc[i] ghi chỉ số phần tử kề trước i trong dãy con dài 
nhất mà i là phần tử cuối dãy.
• Cách tính giá trị trên bảng phương án:
– Gán L[1] = 1 và Truoc[1] = 0
– Với các phần tử i từ 2 đến n: 
• Nếu A[i] < A[j] với mọi j < i thì: L(i) = 1 và Truoc(i) = 0 
• Ngược lại thì
– L(i) = Max{ L(j) : j < i và A[j] <= A[i] } + 1
– Truoc[i] = k sao cho L(k)= Max{ L(j) : j < i và A[j] <= A[i] }
7873343010Truoc[i]
3432232121B[i]
4155-3185-762Dãy A[i]
10987654321I
38
Thuật toán tạo bảng phương án
void TaoBangPhuongAn()
{
L[1] = 1; 
Truoc[1] = 0;
for (i = 2; i <= n; i++)
{ L[i] = 1; 
Truoc[i] = 0;
for (j = i-1; j >= 1; j--)
if (A[j] = L[i])
{ L[i] = L[j] + 1;
Truoc[i] = j;
}
}
}
7873343010Truoc[i]
3432232121L[i]
4155-3185-762A[i]
10987654321I
20
39
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.
7873343010Truoc[i]
3432232121L[i]
4155-3185-762Dãy A[i]
10987654321I
40
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 = n;
for ( j = n-1; j >=1; j--)
if (B[j] > B[i]) i = j;
while ( i > 0) 
{
;
i = Truoc[i];
}
;
}
7873343010Truoc[i]
3432232121B[i]
4155-3185-762A[i]
10987654321I
21
41
Lập lịch thuê nhân công
Có một dự án kéo dài trong T tháng, người quản lý cần phải lập 
lịch sử dụng công nhân mỗi tháng cho dự án. Biết rằng, số công 
nhân tối thiểu cần trong tháng thứ i là Scn[i]; tiền dịch vụ khi thuê 1 
công nhân mới là DV; tiền đền bù khi sa thải một công nhân là ST; 
lương tháng mỗi công nhân phải trả là LT.
Cần phải thuê hay sa thải bao nhiêu công nhân mỗi tháng để tổng 
chi phí nhân công của dự án là nhỏ nhất.
265
11 10 10
T = 3
DV=4; ST= 5; LT=6
Scn={11; 9; 10}
Kết luậnGiả thiết
42
Xác định tham số thể hiện kích thước bài toán 
• Tham số thể hiện kích thước bài toán là số tháng T
• Tổng chi phí nhân công trong T tháng được tính từ tổng chi phí
nhân công của T-1 tháng cộng thêm chi phí trả nhân công của 
tháng thứ T.
• Chi phí trả nhân công của tháng thứ T bao gồm :
– Tiền lương trả cho số nhân công của tháng T và
– Tiền dịch vụ nếu số nhân công của tháng T lớn hơn số nhân 
công tháng T-1 hay tiền sa thải nếu số nhân công trong tháng 
T nhỏ hơn số nhân công của tháng T-1.
• Kích thước bài toán phụ thuộc vào 2 tham số: số tháng và số
nhân công của tháng
22
43
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
44
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
2144+66=280205+60=2654
10
9
11
Scn
155+55+4=214155+50=2053
99+55=16499+50+6=15599+45+12=1562
991
11109i \ j
23
45
Xây dựng bảng truy vết số công nhân
• Mảng Truoc[1..T, 1..Smax]: Truoc[i, j] := k là số người thuê ở
tháng thứ i-1 để có C[i, j]
2144+66=280205+60=2654
10
9
11
Scn
155+55+4=214155+50=2053
99+55=16499+50+6=15599+45+12=1562
991
11109i \ j
10
9
11
Scn
10103
1111112
1
11109i \ j
46
Thuật toán tạo bảng phương án C và Truoc
{ for (j=Scn[1]; j <= Smax; j++) C[1, j] = j * (DV + LT); 
for (i = 2; i <= T; i++)
for (j=Scn[i]; j <= Smax; j++)
{ C[i, j] = MAXINT; 
for (k=Scn[i-1]; k <= Smax; k++)
{ X = C[i-1, k] ;
if (k > j) X = X + (k – j)*DV; else X = X + (j – k)*ST
if (X< C[i, j]) { C[i, j] = X; Truoc[i, j] = k; }
}
}
for (j=Scn[T]; j <= Smax; j++) C[T+1, j] = C(T, j) + (j * ST) ; 
}
24
47
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 <= Smax; j++) 
if (S > C[T+1, j ]) { k = j; S =C[T+1, j ]; }
for (i=T; i > 1; i--) 
{ k = Truoc[i, k];
}
}
48
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.
25
49
6. Việc xây dựng công trình cấp nước sạch ở các bản vùng cao rất khó khăn, phải xây 
dựng kéo hệ thống dẫn nước từ dưới thung lũng lên bản băng qua các ngọn đồi. Để
thuận lợi cho việc dẫn nước, người ta đặt các trạm bơm nối tiếp trên từng ngọn đồi 
dẫn từ thung lũng lên bản vùng cao, theo nguyên tắc ngọn đồi sau phải cao hơn 
ngọn đồi trước, hai trạm bơm kề nhau không nhất thiết đặt trên hai ngọn đồi kề nhau. 
Giả sử có N ngọn đồi (N  100), mỗi ngọn đồi được gán một số thứ tự tăng theo 
hướng từ thung lũng lên vùng cao, ngọn đồi thứ i có độ cao Ai (là một số nguyên 
dương). 
1. Hãy trình bày giải thuật chọn lựa ra các ngọn đồi đặt các trạm bơm sao cho số
ngọn đồi được chọn là nhiều nhất. 
2. Sử dụng Pascal, C/C++, hoặc Java cài đặt giải thuật trên. 
7. Một công ty máy tính nhận được N hợp đồng (N  50) lắp đặt hệ thống máy tính tại N 
công ty. Hợp đồng thứ i có giá trị là Ci (số nguyên) và cần Ai nhân sự để thực hiện. 
Do số lượng nhân sự của công ty có hạn, nên Công ty muốn ưu tiên chọn một số
hợp đồng để thực hiện trước sao cho tổng giá trị của các hợp đồng đã chọn là lớn 
nhất nhưng tổng số nhân sự thực hiện các hợp đồng đó không vượt quá số lượng M 
nhân sự (M  100) hiện có của công ty. Hãy trình bày thuật giải để chọn lựa các hợp 
đồng theo yêu cầu trên, cho biết tổng giá trị của các hợp đồng đã chọn; giá trị hợp 
đồng và số lượng nhân sự của các hợp đồng đã chọn.
50
6. Một công ty máy tính nhận được N hợp đồng (N  50) lắp đặt hệ thống máy tính tại N 
công ty. Hợp đồng thứ i có giá trị là Ci (số nguyên) và cần Ai nhân sự để thực hiện. 
Do số lượng nhân sự của công ty có hạn, nên Công ty muốn ưu tiên chọn một số
hợp đồng để thực hiện trước sao cho tổng giá trị của các hợp đồng đã chọn là lớn 
nhất nhưng tổng số nhân sự thực hiện các hợp đồng đó không vượt quá số lượng M 
nhân sự (M  100) hiện có của công ty. Hãy trình bày thuật giải để chọn lựa các hợp 
đồng theo yêu cầu trên, cho biết tổng giá trị của các hợp đồng đã chọn; giá trị hợp 
đồng và số lượng nhân sự của các hợp đồng đã chọn.