Quy Hoạch Động (Dynamic Programming) Bài toán đồng xu (Coin Change Problem)
Thời gian đọc: 7 phút
Thời gian đọc: 7 phút
Bài toán đồng xu (Coin Change Problem) là một trong những bài toán tối ưu hóa kinh điển trong lập trình, đặc biệt là trong lĩnh vực lập trình động. Mục tiêu của bài toán là tìm cách đổi một số tiền cho trước bằng cách sử dụng số lượng đồng xu ít nhất, dựa trên các mệnh giá đồng xu có sẵn. Thông qua bài toán này, chúng ta không chỉ học được cách giải quyết bài toán tối ưu hóa mà còn hiểu sâu hơn về cách ứng dụng các thuật toán trong thực tế.
Bài toán đồng xu (Coin Change Problem) là một bài toán tối ưu hóa thuộc dạng Dynamic Programming. Mục tiêu của bài toán là tìm cách tối ưu nhất để đổi một số tiền cho trước thành các mệnh giá xu khác nhau, sao cho số lượng đồng xu sử dụng là ít nhất.
Giả sử bạn có một số lượng không giới hạn các đồng xu với mệnh giá khác nhau. Nhiệm vụ của bạn là tìm cách đổi một số tiền cụ thể bằng các đồng xu sao cho số lượng đồng xu sử dụng là ít nhất.
Ví dụ:
Để giải bài toán này, chúng ta sẽ sử dụng Dynamic Programming nhằm tối ưu hóa quá trình tìm cách đổi tiền. Tư duy cơ bản là với mỗi số tiền S, ta sẽ tính toán cách đổi tiền từ các số tiền nhỏ hơn dựa trên các mệnh giá xu có sẵn.
dp mà tại mỗi vị trí dp[i] sẽ lưu trữ số lượng đồng xu ít nhất để đổi được số tiền i.dp[0] = 0 vì không cần đồng xu nào để đổi số tiền 0.Dưới đây là đoạn mã PHP để giải quyết bài toán đổi tiền:
<?php
// Hàm giải quyết bài toán đổi tiền
function coinChange($coins, $amount) {
// Khởi tạo mảng dp với kích thước amount + 1, ban đầu đều là vô cùng
$dp = array_fill(0, $amount + 1, PHP_INT_MAX);
$dp[0] = 0; // Số đồng xu để đổi số tiền 0 là 0
// Duyệt qua tất cả các số tiền từ 1 đến amount
for ($i = 1; $i <= $amount; $i++) {
// Duyệt qua các mệnh giá xu
foreach ($coins as $coin) {
if ($i - $coin >= 0 && $dp[$i - $coin] != PHP_INT_MAX) {
// Cập nhật số lượng đồng xu ít nhất để đổi số tiền i
$dp[$i] = min($dp[$i], $dp[$i - $coin] + 1);
}
}
}
// Nếu không thể đổi được số tiền, trả về -1
return $dp[$amount] == PHP_INT_MAX ? -1 : $dp[$amount];
}
// Mệnh giá đồng xu
$coins = array(1, 2, 5);
// Số tiền cần đổi
$amount = 11;
// Gọi hàm và hiển thị kết quả
$result = coinChange($coins, $amount);
if ($result != -1) {
echo "Số đồng xu ít nhất cần để đổi $amount là: $result";
} else {
echo "Không thể đổi được số tiền $amount với các đồng xu hiện có";
}
?>
$coins: Mảng chứa các mệnh giá đồng xu.$amount: Số tiền cần đổi.dp:
amount.dp[0] được gán bằng 0 vì không cần đồng xu nào để đổi số tiền 0.dp được khởi tạo là PHP_INT_MAX (vô cùng) để đánh dấu những giá trị chưa được tính toán.amount.dp[i] sẽ được cập nhật sao cho nhỏ nhất.dp[$amount] là giá trị lớn hơn PHP_INT_MAX, điều này có nghĩa là không thể đổi số tiền đó, và trả về -1.amount.Khi chạy đoạn mã trên với mệnh giá xu là 1, 2, và 5 và số tiền cần đổi là 11, kết quả sẽ là:
Số đồng xu ít nhất cần để đổi 11 là: 3
Giải pháp tối ưu ở đây là sử dụng 3 đồng xu: 1 đồng xu 5 và 2 đồng xu 2.
Nếu muốn tối ưu hơn cho các trường hợp lớn hơn, bạn có thể:
Bài toán đồng xu (Coin Change Problem) là một ví dụ điển hình về cách sử dụng lập trình động để giải quyết các bài toán tối ưu hóa. Việc tính toán số lượng đồng xu ít nhất để đổi một số tiền giúp ta hiểu sâu hơn về các chiến thuật tối ưu hóa chi phí trong nhiều lĩnh vực như tài chính, vận tải, và hệ thống phân phối. Bằng cách áp dụng giải thuật Dynamic Programming, chúng ta có thể tìm ra giải pháp hiệu quả với độ phức tạp thời gian tối ưu.
Bài toán này có thể mở rộng với các biến thể khác như:
Bài toán đồng xu (Coin Change Problem) là một ví dụ điển hình trong lập trình động, giúp chúng ta giải quyết các bài toán tối ưu hóa phức tạp. Bằng cách áp dụng giải thuật này vào thực tế, bạn có thể tối ưu hóa chi phí, thời gian, và nguồn lực trong nhiều lĩnh vực khác nhau. Việc nắm vững tư duy và cách triển khai bằng PHP sẽ mang lại cho bạn nhiều lợi ích trong việc xây dựng các giải pháp hiệu quả và chính xác cho các bài toán tối ưu hóa.
