Hướng dẫn Thuật Toán Tham Lam (Greedy Algorithm) và ví dụ bằng PHP
Thời gian đọc: 12 phút
Thời gian đọc: 12 phút
Thuật toán tham lam (Greedy Algorithm) là một phương pháp giải quyết vấn đề bằng cách đưa ra các lựa chọn tối ưu nhất ở từng bước mà không cần quan tâm đến các bước tiếp theo. Đây là một kỹ thuật hữu ích cho các bài toán tối ưu hóa, nơi mà bạn muốn tìm một lời giải tốt nhất (tối đa hoặc tối thiểu) trong một tập hợp các lựa chọn.
Nguyên lý chính của thuật toán tham lam là:
Ví dụ điển hình: Bài toán chọn đồng xu có mệnh giá nhỏ nhất để trả tiền thối.
Giả sử bạn có các đồng xu mệnh giá 1, 2, 5 và 10, và bạn cần trả số tiền là 28. Nhiệm vụ của bạn là sử dụng số lượng đồng xu ít nhất.
Ở mỗi bước, bạn sẽ chọn đồng xu có mệnh giá lớn nhất mà vẫn nhỏ hơn hoặc bằng số tiền còn lại.
function minCoins($coins, $amount) {
// Mảng chứa kết quả là các đồng xu được sử dụng
$result = [];
// Sắp xếp các đồng xu theo thứ tự giảm dần
rsort($coins);
foreach ($coins as $coin) {
// Số lượng đồng xu hiện tại có thể sử dụng
while ($amount >= $coin) {
$amount -= $coin;
$result[] = $coin;
}
}
return $result;
}
// Mảng các đồng xu
$coins = [1, 2, 5, 10];
$amount = 28;
$minCoins = minCoins($coins, $amount);
// In kết quả
echo "Số đồng xu ít nhất để trả $amount: ";
print_r($minCoins);
while sẽ trừ đi số tiền tương ứng với đồng xu đang xét cho đến khi không thể trừ thêm được nữa, sau đó chuyển sang đồng xu tiếp theo.
Số đồng xu ít nhất để trả 28: Array
(
[0] => 10
[1] => 10
[2] => 5
[3] => 2
[4] => 1
)
Giả sử bạn có nhiều công việc với thời gian bắt đầu và kết thúc khác nhau. Nhiệm vụ của bạn là tìm số lượng công việc lớn nhất có thể thực hiện mà không trùng lặp thời gian.
Thuật toán tham lam sẽ chọn công việc có thời gian kết thúc sớm nhất, sau đó lặp lại quá trình này cho các công việc còn lại không trùng lặp với công việc đã chọn.
// Hàm lập lịch công việc với thời gian kết thúc sớm nhất
function scheduleJobs($jobs) {
// Sắp xếp công việc theo thời gian kết thúc tăng dần
usort($jobs, function ($a, $b) {
return $a['end'] - $b['end'];
});
$selectedJobs = [];
$lastEndTime = 0;
foreach ($jobs as $job) {
// Nếu thời gian bắt đầu của công việc lớn hơn hoặc bằng thời gian kết thúc của công việc trước đó
if ($job['start'] >= $lastEndTime) {
$selectedJobs[] = $job;
$lastEndTime = $job['end'];
}
}
return $selectedJobs;
}
// Danh sách các công việc với thời gian bắt đầu và kết thúc
$jobs = [
['start' => 1, 'end' => 3],
['start' => 2, 'end' => 5],
['start' => 4, 'end' => 6],
['start' => 6, 'end' => 8],
['start' => 5, 'end' => 7]
];
$selectedJobs = scheduleJobs($jobs);
// In ra các công việc đã chọn
echo "Danh sách công việc có thể thực hiện: ";
print_r($selectedJobs);
Danh sách công việc có thể thực hiện: Array
(
[0] => Array
(
[start] => 1
[end] => 3
)
[1] => Array
(
[start] => 4
[end] => 6
)
[2] => Array
(
[start] => 6
[end] => 8
)
)
Mặc dù thuật toán tham lam rất nhanh và hiệu quả trong việc đưa ra các giải pháp, nhưng không phải lúc nào nó cũng tìm được lời giải tối ưu cho tất cả các loại bài toán. Để áp dụng thuật toán tham lam thành công, bạn cần đảm bảo rằng bài toán của mình thỏa mãn các tính chất sau:
Ví dụ, với bài toán tìm đường đi ngắn nhất trong đồ thị (Shortest Path), thuật toán tham lam như Dijkstra sẽ hoạt động tốt, nhưng với bài toán “balo” (Knapsack Problem), thuật toán tham lam không luôn đảm bảo tìm ra lời giải tối ưu.
Thuật toán tham lam là một kỹ thuật hữu ích và hiệu quả để giải quyết nhiều bài toán trong lập trình. Bằng cách đưa ra các quyết định tối ưu tại mỗi bước, bạn có thể giảm thiểu thời gian và tài nguyên cần thiết để tìm ra giải pháp. Tuy nhiên, cần phải hiểu rõ bản chất của bài toán để đảm bảo rằng việc áp dụng thuật toán tham lam sẽ đưa ra kết quả tốt nhất.
Việc áp dụng thuật toán tham lam trong PHP, như đã minh họa qua các ví dụ ở trên, cho thấy rằng chúng ta có thể sử dụng ngôn ngữ này để triển khai các giải pháp tối ưu một cách dễ dàng và linh hoạt.
Dưới đây là một ví dụ nâng cao về thuật toán tham lam, được minh họa qua bài toán “Bài toán cái túi (Knapsack Problem) dạng phân số” (Fractional Knapsack Problem). Đây là một trong những bài toán cổ điển và phổ biến nhất trong lý thuyết thuật toán tham lam.
Giả sử bạn có một cái túi với sức chứa giới hạn W. Có n đồ vật, mỗi đồ vật có trọng lượng w[i] và giá trị v[i]. Nhiệm vụ của bạn là chọn các đồ vật để bỏ vào túi sao cho tổng giá trị là lớn nhất, nhưng trọng lượng của các đồ vật không vượt quá giới hạn của túi. Điều đặc biệt ở dạng bài toán này là bạn có thể chia đồ vật ra, nghĩa là bạn có thể chọn một phần của một đồ vật.
v[i] / w[i]) cao nhất trước.value/weight cho mỗi đồ vật.
// Hàm để giải bài toán cái túi dạng phân số
function fractionalKnapsack($capacity, $items) {
// Tính giá trị trên một đơn vị trọng lượng và sắp xếp theo thứ tự giảm dần
usort($items, function($a, $b) {
return ($b['value'] / $b['weight']) <=> ($a['value'] / $a['weight']);
});
$totalValue = 0.0;
$result = [];
foreach ($items as $item) {
// Nếu trọng lượng của đồ vật nhỏ hơn hoặc bằng dung lượng còn lại của túi
if ($item['weight'] <= $capacity) {
// Chọn toàn bộ đồ vật
$capacity -= $item['weight'];
$totalValue += $item['value'];
$result[] = [
'item' => $item,
'fraction' => 1.0
];
} else {
// Chọn một phần đồ vật để lấp đầy túi
$fraction = $capacity / $item['weight'];
$totalValue += $item['value'] * $fraction;
$result[] = [
'item' => $item,
'fraction' => $fraction
];
break; // Đã đầy túi, dừng lại
}
}
return [
'total_value' => $totalValue,
'selected_items' => $result
];
}
// Danh sách các đồ vật với trọng lượng và giá trị
$items = [
['weight' => 10, 'value' => 60],
['weight' => 20, 'value' => 100],
['weight' => 30, 'value' => 120]
];
$capacity = 50; // Sức chứa của túi
$result = fractionalKnapsack($capacity, $items);
// In ra tổng giá trị tối đa có thể lấy
echo "Giá trị lớn nhất có thể lấy được: " . $result['total_value'] . "\n";
// In ra các đồ vật đã được chọn và phần trăm của chúng
echo "Danh sách đồ vật được chọn:\n";
foreach ($result['selected_items'] as $selected) {
$item = $selected['item'];
$fraction = $selected['fraction'] * 100;
echo "Đồ vật có trọng lượng {$item['weight']} và giá trị {$item['value']} được chọn $fraction%.\n";
}
usort() sắp xếp các đồ vật theo tỷ lệ value/weight giảm dần.
Giá trị lớn nhất có thể lấy được: 240
Danh sách đồ vật được chọn:
Đồ vật có trọng lượng 10 và giá trị 60 được chọn 100%.
Đồ vật có trọng lượng 20 và giá trị 100 được chọn 100%.
Đồ vật có trọng lượng 30 và giá trị 120 được chọn 33.333333333333%.
Trong ví dụ này:
Bài toán “Cái túi dạng phân số” thường được sử dụng trong các tình huống thực tế như:
Thuật toán tham lam rất mạnh mẽ khi giải quyết các bài toán tối ưu hóa, đặc biệt là khi các bài toán có thể chia nhỏ thành các phần con độc lập. Bài toán “Cái túi dạng phân số” là một ví dụ điển hình về cách thuật toán tham lam có thể giúp đưa ra giải pháp tối ưu bằng cách đưa ra quyết định tốt nhất tại mỗi bước.
