Giáo trình Cấu trúc dữ liệu và thuật giải 2 - Nguyễn Thị Thanh Bình (Phần 2)

ừ điển. 
Bài tập 
1. Hãy cài đặt hàm băm sử dụng phương pháp nhân mục II.2. 
2. Hãy cài đặt hàm thăm dò sử dụng phương pháp băm kép. 
3. Giả sử cỡ của bảng băm là SIZE = s và d1, d2, , ds-1 là hoán vị ngẫu nhiên 
của các số 1, 2, , s-1. Dãy thăm dò ứng với khoá k được xác định như sau: 
i0 = i = h(k) 
im = (i + di) % SIZE , 1 ≤ m≤ s –1 
Hãy cài đặt hàm thăm dò theo phương pháp trên. 
4. Cho cỡ bảng băm SIZE = 11. Từ bảng băm rỗng, sử dụng hàm băm chia 
lấy dư, hãyđưa lần lượt các dữ liệu với khoá: 
32 , 15 , 25 , 44 , 36 , 21 
vào bảng băm và đưa ra bảng băm kết quả trong các trường hợp sau: 
b. Bảng băm được chỉ mở với thăm dò tuyến tính. 
c. Bảng băm được chỉ mở với thăm dò bình phương. 
d. Bảng băm dây chuyền. 
5. Từ các bảng băm kết quả trong bài tập 4, hãy loại bỏ dữ liệu với khoá là 44 
rồi sau đó xen vào dữ liệu với khoá là 65. 
6. Bảng băm chỉ cho phép thực hiện hiệu quả các phép toán tập động nào? 
Không thích hợp cho các phép toán tập động nào? Hãy giải thích tại sao? 
73 
7. Giả sử khoá tìm kiếm là từ tiếng Anh. Hãy đưa ra ít nhất 3 cách thiết kế 
hàm băm. Bình luận về các cách thiết kế đó theo các tiêu chuẩn hàm băm 
tốt. 
74 
Chương IV 
Một số phương pháp thiết kế thuật giải 
cơ bản 
Mục tiêu 
Sau khi học xong chương này, sinh viên nắm được một số phương pháp thiết kế giả 
thuật cơ bản, cài đặt và vận dụng để giải một số bài toán thực tế. 
Kiến thức cơ bản cần thiết 
Để học tốt chương này sinh viên cần phải nắm vững kỹ năng lập trình cơ bản như: 
- Các cấu trúc điều khiển, lệnh vòng lặp. 
- Lập trình hàm, thủ tục, cách gọi hàm. 
- Lập trình đệ qui và gọi đệ qui. 
Nội dung 
Trong chương này chúng ta sẽ nghiên cứu một số phương pháp thiết kế giải thuật cơ 
bản như sau: 
- Phương pháp chia để trị 
- Phương pháp quay lui 
- Phương pháp tham lam 
I. Phương pháp chia để trị 
1. Mở đầu 
Ý tưởng: 
Có lẽ quan trọng và áp dụng rộng rãi nhất là kĩ thuật chia để trị. Nó phân rã bài toán 
kích thước n thành các bài toán nhỏ hơn mà việc tìm lời giải của chúng là cùng một 
cách. Lời giải của bài toán lớn được xây dựng từ lời giải của các bài toán con này. 
Ta có thể nói vắn tắt ý tưởng chính của phương pháp này là: chia dữ liệu thành từng 
miền nhỏ, giải bài toán trên các miền đã chia rồi tổng hợp kết quả lại. 
Mô hình 
Nếu gọi D&C(ℜ ) với ℜ là miền dữ liệu là hàm thể hiện cách giải bài toán theo 
phương pháp chia để trị thì ta có thể viết: 
Void D&C(ℜ ) 
{ 
75 
 If(ℜ đủ nhỏ) 
 Giải bài toán 
 Else 
 { 
 Chia ℜ thành ℜ 1, .., ℜ m; 
 For(j=1; j<=m; j++) 
 D&C(ℜ j); 
 Tổng hợp kết quả; 
 } 
} 
Sau đây là một số ví dụ minh họa cho phương pháp chia để trị 
2. Tìm kiếm nhị phân 
Phát biểu bài toán 
Cho mảng n phần tử đã được sắp xếp tăng dần và một phần tử x. Tìm x có trong mảng 
hay không? Nếu có trả về kết quả là 1, ngược lại trả về kết quả là 0. 
Ý tưởng 
Chia đôi mảng, mỗi lần so sánh phần tử giữa với x, nếu phần tử giữa nhỏ hơn x thì tìm 
x ở nửa bên phải, ngược lại thì tìm x ở nửa bên phải. 
Mô tả thuật toán 
Input: a[1..n] 
Output: 
1: nếu x thuộc a 
0: nếu x không thuộc a 
Mô tả: 
TKNP(a, x, đầu, cuối)≡ 
 If(đầu > cuối) 
 Return 0; 
 Else 
 { 
 giữa = (đầu + cuối)/2; 
 If(x == a[giữa]) 
 Return 1; 
 Else if(x > a[giữa]) 
76 
 TKNP(a, x, giữa +1, cuối); 
 Else TKNP(a, x, đầu, giữa-1); 
 } 
Độ phức tạp của thuật toán 
Trường hợp tốt nhất: ứng với trường hợp tìm thấy x trong lần so sánh đầu tiên. Ta có: 
 Ttốt (n) = O(1) 
Trường hợp xấu nhất: độ phức tạp là O(lgn). Thật vậy, nếu gọi T(n) là độ phức tạp của 
thuật toán, thì sau khi kiểm tra điều kiện (x == a[giữa]) không thỏa và gọi đệ quy thuật 
toán này với dữ liệu giảm đi một nửa, thỏa mãn công thức truy hồi: 
 T(n) = 1+T(n/2); n>=2 và T[1]=0. 
3. Bài toán Min-Max 
Phát biểu bài toán 
Tìm min-max trong đoạn a[l..r] của mảng a[1..n] 
Ý tưởng 
Tại mỗi bước chia đôi đoạn cần tìm rồi tìm min, max của từng đoạn, sau đó tổng hợp 
kết quả lại. 
Nếu đoạn chia chỉ có một phần tử thì min = max và bằng phần tử đó. 
Ví dụ minh họa: 
J 1 2 3 4 5 6 7 8 
a[j] 10 1 5 0 9 3 15 19 
Tìm giá trị min, max trong đoạn a[2..7]. 
Ki hiệu: 
MinMax(a,l,r,Min, Max) cho Min, Max trong đoạn a[l..r]. 
MinMax(a,2,7,Min,Max) cho Min=0, Max=15 trong đoạn a[2..7] 
Mô tả thuật toán 
Input: a[l..r] (l<=r) 
Output: 
 Min = min(a[l]a[r]) 
 Max = max(a[l]..a[r]) 
Mô tả: 
MinMax(a,l,r,Min,Max) 
 If(l==r) 
77 
 { 
 Min = a[l]; 
 Max = a[l]; 
 } 
 Else 
 { 
 MinMax(a,l,(l+r)/2,Min1,Max1) 
 MinMax(a,(l+r)/2,r,Min2,Max2) 
 If(Min1<Min2) 
 Min = Min1; 
 Else Min = Min2; 
 If(Max1<Max2) 
 Max = Max2; 
 Else Max = Max1; 
 } 
Độ phức tạp thuật toán 
Gọi T(n) là số phép so sánh cần thực hiện. Khi đó ta có: 
T(n) =
⎪⎩
⎪⎨
⎧
=
=
>++
1;0
2;1
2;2)2/()2/(
n
n
nnTnT
Với n = 2k, thì: 
T(n) = 2 + 2T(n/2) = 2+ 22 + 22T(n/22) =  = 2k-1T(2)+∑−
=
1
1
k
i
2i = 
=∑−
=
1
1
k
i
2i – 2k-1 = 2k+1 – 2k-1 - 2 = 3n/2 – 2. 
Vậy T(n) ∈O(n). 
4. Thuật toán QuickSort 
Phát biểu bài toán 
Sắp xếp một mảng không có thứ tự thành một màng có thứ tự xác định,chẳng hạn tăng 
hoặc giảm. 
Ý tưởng 
Chọn ngẫu nhiên một phần tử x. 
Duyệt dãy từ bên trái (theo chỉ số i) trong khi ai < x. 
78 
Duyệt dãy từ bên phải (theo chỉ số j) trong khi aj > x. 
Đổi chỗ a[i] và a[j] nếu hai phía chưa vượt qua nhau, .. tiếp tục quá trình duyệt và đổi 
chỗ như trên trong khi hai phía còn chưa vượt qua nhau (tức là i<=j). 
Kết quả phân hoạch dãy thành 3 phần: 
ak <=x với k = 1..j (dãy con thấp); 
am >=x với m = i..n (dãy con cao); 
ah = x với h = j+1..i-1. 
Vì vậy phương pháp này còn gọi là sắp xếp phân hoạch 
 ak x am 
Tiếp tục phân hoạch cho phần trái và phần phải cho đến khi các phân hoạch chỉ còn lại 
một phần tử là sắp xếp xong. 
Mô tả thuật toán: 
Input: a[l..r] 
Output: a[l..r] không giảm 
QuickSort(a,l,r) 
{ 
 i=l; 
 j=r; 
 x= a[(l+r)/2];//chọn phần tử giữa 
 do 
 { 
 While(a[i]<x) i++; 
 While(a[j]>x)j--; 
 If(i<=j) 
 { 
 Đổi chỗ a[i] và a[j]; 
 i++; 
 j--; 
 } 
 }while(i<=j) 
 If(l<=j) QuickSort(a,l,j); 
 If(i<=r) QuickSort(a,i,r); 
79 
} 
Độ phức tạp thuật giải 
Điều tốt nhất có thể xảy ra trong QuickSort mỗi giai đoạn phân hoạch chia mảng thành 
hai nửa. Điều này khiến cho số lần so sánh cần thiết của QuickSort thỏa mãn công 
thức sau đây: 
 Tn = 2Tn/2 + n = nlgn. 
2Tn/2: phí tổn sắp xếp 2 mảng con. 
n: phí tổn kiểm tra mỗi phần tử 
Trường hợp xấu nhất ứng cho việc chọn phần tử x lại có giá trị lớn nhất hoặc nhỏ nhất 
trong dãy. Giả sử phần tử lớn nhất được chọn (x), khi đó mỗi bước chia sẽ chia n phần 
tử thành n-1 phần tử trái và 1 phần tử phải. Kết quả cần tới n phép chia (thay cho nlgn) 
và như thế độ phức tạp sẽ là T(n) = O(n2). 
Trong trường hợp này dãy đã có thứ tự thuận hay ngược, phần tử lớn nhất được chọn 
sẽ nằm ở các biên (trái hoặc phải), nên thuật toán không có hiệu quả. 
Trường hợp trung bình, công thức truy hồi để tính số lần so sánh mà thuật toán cần để 
hoán vị ngẫu nhiên n phần tử là: 
T(n) = (n+1) + ∑
<=<= nkn 1
1 (Tk-1 + Tn-k); với n>=2; C0 = C1 = 1; 
Giá trị n+1 bao hàm chi phí so sánh phần tử phân hoạch với mỗi phần tử còn lại, tổng 
còn lại mang ý nghĩa là mỗi phần tử k có thể là phần tử phân hoạch với xác suất 1/k và 
sau đó còn lại các mảng con có kích thước k-1 và n-k. 
Tn = n+1+ ∑
=
n
kn 1
2 Tk-1 
Thực hiện liên tiếp các phép toán sau cho cả hai vế: nhân n và trừ cho (n-1)Cn-1: 
nTn – (n-1)Tn-1 = n(n-1) + ∑
=
n
kn 1
2 Tk-1 – (n-1)Tn-1 
= n(n+1) + ∑
=
n
kn 1
2 Tk-1 – (n-1)[n + ∑−
=−
1
11
2 n
kn
Tk-1] 
= n(n+1) – n(n-1) + 2 ∑
=
n
k 1
Tk-1 - 2∑−
=
1
1
n
k
Tk-1 
Ta được: nTn – (n-1)Tn-1 = n(n+1) – n(n-1)+ 2Tn-1 
Suy ra: nTn = (n+1)Tn-1 + 2n 
Nhân cả hai vế cho n(n+1): 
Tn/(n+1) = Tn-1/n + 2/(n+1) = Tn-2/(n-1)+ 2/n + 2/(n+1) 
80 
= 2/(n+1) + 2/n+2/4+2/3+T1/2 = 1/2 + 2 ∑
= +
n
k k2 1
2 
= 1/2 + 2 ∑+
=
1
3
1n
k k
Tn/(n+1) ≡ 2 ∑+
=
1
3
1n
k k
 ≡2 ∫n dxx1
1 = 2ln(n) 
Như vậy độ phức tạp trung bình là O(nlnn) 
II. Phương pháp quay lui 
1. Mở đầu 
Ý tưởng 
Nét đặc trưng của phương pháp quay lui là các bước hướng tới lời giải cuối cùng của 
bài toán đều được làm thử. 
Tại mỗi bước nếu có một lựa chọn được chấp nhận thì ghi nhận lại lựa chọn này và 
tiến hành các bước thử tiếp theo. Còn ngược lại không có sự lựa chọn nào thích hợp 
thì làm lại bước trước, xóa bỏ ghi nhận và quay về chu trình thử các lựa chọn còn lại. 
Hành động này được gọi là quay lui, thuật toán thể hiện phương pháp này gọi là quay 
lui. 
Điểm quan trọng của thuật toán là phải ghi nhớ lại mỗi bước đi qua để tránh trùng lặp 
khi quay lui. Dễ thấy là các thông tin này cần được lưu trữ vào một ngăn xếp, nên 
thuật toán thể hiện một cách đệ quy. 
Mô hình 
Lời giải của bài toán thường được biểu diễn bằng một vector gồm n thành phần x= (x1, 
..xn) phải thỏa các điều kiện nào đó. Để chỉ ra lời giải x ta phải xây dựng các thành 
phần lời giải xi. 
Tại mỗi bước i: 
Đã xây dựng xong các thành phần x1..xi-1. 
Xây dựng thành phần xi bằng cách lần lượt thử các khả năng mà xi có thể chọn: 
- Nếu một khả năng j nào đó phù hợp với xi thì xác định xi theo khả năng 
j. Thường phải có thêm thao tác ghi nhận trạng thái mới của bài toán để 
hỗ trợ cho bước quay lui. Nếu i = n thì ta có được một lời giải, ngược lại 
thì tiến hành bước i+1 để xác định xi+1. 
- Nếu không có một khả năng nào chấp nhận được cho xi thì ta lùi lại 
bước trước (bước i-1) để xác định lại thành phần xi-1. 
Để đơn giản ta có thể giả định các khả năng chọn lựa cho các xi tại mỗi bước là như 
nhau, do đó ta phải có thêm thao tác kiểm tra khả năng j nào chấp nhận được cho xi. 
81 
Mô hình của phương pháp quay lui có thể viết bằng thủ tục như sau, với n là số bước 
cần phải thực hiện, k là số khả năng mà xi có thể chọn lựa 
Try(i)≡ 
For(j=1Æk) 
 If(xi chấp nhận được khả năng j) 
 { 
 Xác định xi theo khả năng j; 
 Ghi nhận trạng thái mới; 
 If(i<n) 
 Try(i+1); 
 Else 
 Ghi nhận nghiệm; 
 Trả lại trạng thái cũ cho bài toán; 
 } 
2. Bài toán liệt kê dãy nhị phân độ dài n 
Phát biểu bài toán 
Liệt kê dãy có chiều dài n dưới dạng x1,x2,..,xn trong đó xi thuộc {0,1} 
Thiết kế thuật toán 
Ta có thể sử dụng sơ đồ tìm tất cả lời giải của bài toán. Hàm Try(i) xác định xi, trong 
đó xi chỉ có một trong hai giá trị 0 hoặc 1. Hàm Try(i) có thể viết như sau: 
Try(i) 
{ 
 For(j=0; j<=1; j++) 
 { 
 x[i] = j; 
 if(i<n) 
 Try(i+1); 
 Else Xuất x. 
 } 
} 
3. Bài toán liệt kê các hoán vị 
Phát biểu bài toán 
Liệt kê các hoán vị của n số nguyên duơng đầu tiên 
82 
Thiết kế thuật toán 
Ta biểu diễn các hoán vị dưới dạng a1,..,an; ai ∈ {1,..,n}, ai ≠ aj nếu i ≠ j . Với 
mọi i, ai chấp nhận giá trị j nếu j chưa được sử dụng và vì vậy ta cần ghi nhớ j đã được 
sử dụng hay chưa khi quay lui. Để làm điều này ta sử dụng một dãy các biến logic bj 
với quy ước: 
 ;,1 nj =∀ bj = ⎪⎩
⎪⎨
⎧
;0
;1
Sau khi gán j cho ai, ta cần ghi nhớ bj (bj = 0) và phải trả lại trạng thái cũ cho bj (bj =1) 
khi thực hiện việc in xong một hoán vị. 
Ta cần chú ý rằng dãy các biến bj sẽ được khởi động bằng 1. 
Thuật toán 
Try(i) 
{ 
 For(j=1; j<=n; j++) 
 { 
 If(b[j]) 
 { 
 a[i] = j; 
 b[j] = 0; 
 if(i<n) 
 Try(i+1); 
 Else Xuất; 
 b[j] = 1; 
 } 
} 
4. Bài toán duyệt đồ thị theo chiều sâu (DFS) 
Phát biểu bài toán 
G = (V,U) là đơn đồ thị (có hướng hoặc vô hướng). V: tập các đỉnh của đồ thị, U là 
tập các cung cũa đồ thị. Với s, t là hai đỉnh của đồ thị, tìm tất cả các đường đi từ s đến 
t. 
Ý tưởng 
Thuật toán DFS tiến hành tìm kiếm trong đồ thị theo chiều sâu. Thuật toán thực hiện 
việc thăm tất cả các đỉnh có thể đạt được cho tới đỉnh t từ đỉnh s cho trước. Đỉnh được 
Nếu j chưa sử dụng 
Nếu j đã sử dụng 
83 
thăm càng muộn sẽ càng sớm được duyệt xong (cơ chế vào sau ra trước). Nên thuật 
toán có thể tổ chức bằng một thủ tục đệ quy quay lui. 
Mô tả thuật toán 
Input: G = (V,U), s,t 
Output: Tất cả các đường đi từ s đến t.(nếu có) 
DFS(int s) 
{ 
 For(u=1; u<=n; u++) 
 If(chấp nhận được) 
 { 
 Ghi nhận nó; 
 If(u != t) 
 DFS(u); 
 Else Xuất đường đi 
 Bỏ việc ghi nhận; 
 } 
} 
Ví dụ: Cho đồ thị có hướng với ma trận kề sau: 
 7 
0 0 0 1 0 1 1 
0 0 1 1 0 0 0 
0 1 0 1 0 1 0 
1 0 1 0 0 0 0 
0 0 0 0 1 1 0 
1 0 0 0 1 0 0 
1 0 0 1 0 0 0 
Kết quả: 
s=1, t=4 s=2, t = 5 
1Æ4 
1Æ7Æ4 
2Æ3Æ4Æ1Æ6Æ5 
2Æ3Æ6Æ5 
2Æ4Æ1Æ6Æ5 
2Æ4Æ3Æ6Æ5 
84 
III. Phương pháp tham lam 
1. Mở đầu 
Ý tưởng 
Phương pháp tham lam là kĩ thuật thiết kế thường được dùng để giải các bài toán tối 
ưu. Phương pháp được tiến hành trong nhiều bước. Tại mỗi bước, theo một chọn lựa 
nào đó (xác định bằng một hàm chọn), sẽ tìm một lời giải tối ưu cho bài toán nhỏ 
tương ứng. Lời giải của bài toán được bổ sung dần từng bước từ lời giải của các bài 
toán con. 
Các lời giải bằng phương pháp tham lam thường chỉ là chấp nhận được theo điều kiện 
nào đó, chưa chắc đã tối ưu. 
Cho trước một tập A gồm n đối tượng, ta cần phải chọn ra một tập con S của A. Với 
một tập con S được chọn ra thỏa mãn yêu cầu của bài toán, ta gọi là một nghiệm chấp 
nhận được. Một hàm mục tiêu gán mỗi nghiệm chấp nhận được với một giá trị. 
Nghiệm tối ưu là nghiệm chấp nhận được mà tại đó hàm mục tiêu đạt giá trị nhỏ nhất 
(lớn nhất). 
Đặc trưng tham lam của phương pháp thể hiện bởi: trong mỗi bước việc xử lý sẽ tuân 
theo một sự chọn lựa trước, không kể đến tình trạng không tốt có thể xảy ra. 
Mô hình 
Chọn S từ tập A. 
Tính chất tham lam của thuật toán được định hướng bởi hàm chọn 
Khởi động: S = rỗng 
Trong khi A khác rỗng 
Chọn phần tử tối ưu nhất của A gán vào x : x = chọn(A); 
Cập nhật các đối tượng để chọn: A = A-{x}; 
Nếu S∪ {x} thỏa mãn yêu cầu của bài toán thì cập nhật lời giải: S = S∪ {x}; 
Thủ tục tham lam 
Input: A[1..n] 
Output: lời giải S 
Greedy(A,n) 
{ 
 S = Rỗng; 
 While(A ≠ Rỗng) 
 { 
 A = A-{x}; 
85 
 If(S∪ {x} chấp nhận được) 
 S = S∪ {x}; 
 } 
 Return S; 
} 
2. Bài toán người du lịch 
Phát biểu bài toán 
Một người du lịch muốn tham quan n thành phố T1, .., Tn. Xuất phát từ một thành phố 
nào đó và đi qua tất cả các thành phố còn lại, mỗi thành phố qua đúng một lần và quay 
về thành phố xuất phát. 
Gọi Cij là chi phí chi từ thành phố Ti đến thành phố Tj. Hãy tìm một hành trình thỏa 
yêu cầu bài toán với chi phí nhỏ nhất. 
Ý tưởng 
Đây là bài toán tìm chu trình có trọng số nhỏ nhất trong một đồ thị đơn có hướng có 
trọng số. 
Thuật toán tham lam cho bài toán là chọn thành phố có chi phí nhỏ nhất tính từ thành 
phố hiện thời đến các thành phố chưa đi qua. 
Mô tả thuật toán 
Input: C = Cij 
Output: TOUR //Hành trình tối ưu 
COST //Chi phí tương ứng 
TOUR = 0; 
COST = 0; v = u; 
1=∀k Æn 
Chọn là đoạn nối hai thành phố có chi phí nhỏ nhất tính từ thành phố v đến 
các thành phố chưa qua. 
TOUR = TOUR + ; 
COST = COST + Cvw 
Hoàn thành chuyến đi 
TOUR = TOUR + ; 
COST = COST + Cvu 
Độ phức tạp thuật toán 
86 
Thao tác chọn đỉnh thích hợp trong n đỉnh được tổ chức bằng một vòng lặp để duyệt, 
nên chi phí cho thuật toán xác định bởi hai vòng lặp lồng nhau, nên độ phức tạp T(n) 
∈O(n2). 
Cài đặt 
 int GTS(matra a, int n, int Tour[max], int Ddau) 
{ 
 int v, k, w; 
 int min; 
 int cost; 
 int daxet[max]; 
 for (int k = 1; k <= n; k++) 
 daxet[k] = 0; 
 cost = 0; 
 int i; 
 v = Ddau; 
 int i = 1; 
 Tour[i] = v; 
 daxet[v] = 1; 
 while (i < n) 
 { 
 min = VC; 
 for (int k = 1; k <= n; k++) 
 { 
 if(daxet[k]) 
 if (min > a[v][k]) 
 { 
 min = a[v][k]; 
 w = k; 
 } 
 v = w; 
 i++; 
 Tour[i] = v; 
 daxet[v] = 1; 
87 
 cost = cost + min; 
 } 
 } 
 cost = cost + a[v][Ddau]; 
 return cost; 
} 
3. Thuật toán Prim - Tìm cây bao trùm nhỏ nhất 
 (trình bày trong chương Đồ thị) 
4. Bài toán chiếc túi sách 
Phát biểu bài toán 
Có n vật, mỗi vật i, i∈[1..n] được đặc trưng bởi trọng lượng wi(kg) và giá trị sử dụng 
vi. Có một chiếc túi xách có khả năng mang m kg. Giả sử wi, vi, m∈N*, ∀ i∈[1..n]. 
Hãy chọn vật xếp vào túi sao cho túi sách thu được giá trị sử dụng lớn nhất. 
Các trọng lượng của n vật có thể biểu diễn bởi mảng: 
 w = (w1,w2,..,vn) 
Và giá trị sử dụng tượng ứng với các vật: 
 v = (v1,v2,,vn) 
Các vật được chọn được lưu trữ vào một mảng ε với quy ước: ε [i] = 1 tức là vật i 
được chọn. 
Bài toán trở thành: 
{ }⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
=∀∈
≤
→
∑
∑
=
=
ni
mv
v
i
n
i
ii
n
i
ii
,1,1,0
max
1
1
ε
ε
ε
Thiết kế thuật toán 
Thuật toán tham lam cho bài toán chọn vật có giá trị giảm dần (theo đơn giá). 
Input: 
 w = (w1,w2,..,vn); //Mảng trọng lượng các vật 
 v = (v1,v2,,vn); //Mảng giá trị các vật 
 m: sức chứa của ba lô 
Output: 
88 
 ε [1..n]; //mảng đánh dấu các vật được chọn 
 Vmax: giá trị lớn nhất 
Mô tả 
Knap_Greedy(w,v,Chon,n,m) 
{ 
Khởi động b[i] = i, ni ,1=∀ ; //Lưu trữ chỉ số làm cho mảng giảm dần 
Khởi động Chon[i] = 0, ni ,1=∀ ;//Mảng đánh dấu vật được chọn 
Khởi động Vmax=0; 
Tính đơn giá: di = 
i
i
w
v , ni ,1=∀ 
For(i=1; i0; i++) 
 { 
 j = max(d,n,i); // d[j] = Max{d[i],,d[n]}; 
 b[i]↔b[j] 
 if(m>w[b[i]]) 
 { 
 Vmax+=v[b[i]]; 
 Chon[b[i]] = 1; 
 M-=w[b[i]]; 
 } 
 d[i]↔d[j] 
 } 
Return Vmax 
} 
Độ phức tạp thuật toán 
Thuật toán chọn max được sử dụng chính là thuật toán chọn trực tiếp, nên độ phức tạp 
của thuật toán trong các trường hợp là O(n2). 
Bài tập 
1. Cài đặt các thuật toán trình bày trong giáo trình 
2. Nhân các số lớn 
Kỹ thuật chia để trị nhân 2 số nguyên dương x, y dưới dạng chuỗi: 
Nhan(x, y) 
89 
 If(l(x) và l(y) <=4) // chiều dài nhỏ hơn 4 
 Nhân hai số nguyên kiểu long 
 Else 
 Giả sử l(x) = l(y) = n; 
 Tách thành x hai chuỗi con: a(nửa trái), b(nửa phải) 
 Tách thành y hai chuỗi con: c(nửa trái), d(nửa phải) 
 Kq = Nhan(a,c)*10n + Nhan(a,d)*10n/2 + Nhan(b,c)*10n/2 + Nhan(b,d) 
3. Sắp tăng dần một dãy x các số bằng thuật toán trộn tự nhiên: 
 Trong khi (số đường chạy của x >1) 
- Tách luân phiên đường chạy của x vào hay dãy trung gian x1,x2. 
- Trộn từng cặp đường chạy của x1, x2, lưu vào x 
4. Giả sử ổ khóa có n công tắc. Mỗi công tắc ở một trong hai trạng thái đóng hoặc mở. 
Khóa được mở nếu có ít nhất n/2 công tắc ở trạng thái mở. Liệt kê tất cả các cách mở 
khóa 
5. Một người muốn tham quan qua n thành phố T1, , Tn. Xuất phát từ một thành phố 
nào đó, người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đi qua 
đúng một lần rồi quay lại thành phố xuất phát. 
Gọi Cij là chi phí đi từ thành phố Ti đến thành phố Tj. 
- Liệt kê tất cả các hành trình mà người đó có thể đi và kèm theo chi phí tương 
ứng. 
- Chỉ ra hành trình đi từ thành phố từ Ti đến thành phố Tj thỏa yêu cầu bài toán 
(nếu có) sao cho chi phí thấp nhất. 
6. Cho một lưới hình vuông cấp n, mỗi ô được gán với một số tự nhiên. Tại một ô có thể 
di chuyển đến ô khác theo hướng lên trên, xuống dưới, qua trái, qua phải. 
Tìm đường đi từ ô đầu tiên (1,1) đến ô (m, m) sao cho tổng các ô đi qua là nhỏ nhất. 
(1<=m <= n) 
7. bài toán đổi tiền xu. 
Có một đồng xu giá trị là n. Hãy đổi thành các đồng xu có giá trị 1 xu, 5 xu, 10 xu, 20 
xu, 25 xu sao cho tổng số đồng xu là ít nhất. 
90 
Tài liệu tham khảo 
1. Alfred V. Aho, John E. Hopcroft và Jeffrey D. Ullman 
 “Data Structures and Algorithms” 
 Addison Wesley Publishing Company, 1987 
2. Donald Knuth, “The art of computer programming” 
 Vol1: Fundamental algorithms 
 Vol3: Sorting and searching 
 Addison Wesley Publishing Company, 1973 
3. Niklaus Wirth, “Algorithms + Data structures = programs” 
 Prentice Hall INC, 1976 
4. Nguyễn Xuân Huy, “Thuật toán”, Nhà xuất bản thống kê, Hà Nội, 1988. 
5. Trương Chí Tín, giáo trình “Cấu trúc dữ liệu và thuật giải 2”, Đại học Đà 
Lạt, 2002. 
6. Nguyễn Văn Linh, Trần Cao Đệ, Trương Thị Thanh Tuyền, Lâm Hoài Bảo, 
Phan Huy Cường, Trần Ngân Bình, giáo trình “Cấu trúc dữ liệu”, Đại học 
Cần Thơ, 2003 của các tác giả.