Quy Hoạch Động (Dynamic Programming) Bài toán xếp ba lô (Knapsack Problem)
Thời gian đọc: 7 phút
Thời gian đọc: 7 phút
Bài toán xếp ba lô (Knapsack Problem) là một trong những bài toán tối ưu hóa cổ điển. Mục tiêu của bài toán này là chọn một tập hợp các đối tượng có trọng lượng và giá trị khác nhau để bỏ vào một chiếc ba lô có giới hạn trọng lượng sao cho tổng giá trị của các đối tượng là lớn nhất.
Giả sử bạn có một chiếc ba lô với sức chứa cố định, và bạn có một tập các đối tượng với giá trị và trọng lượng khác nhau. Nhiệm vụ của bạn là chọn các đối tượng để bỏ vào ba lô sao cho:
Đây là dạng bài toán phổ biến nhất. Trong dạng này, mỗi đối tượng có thể được chọn hoặc không được chọn (0 hoặc 1).
Đây là biến thể mà bạn có thể chọn một phần của đối tượng, thay vì phải chọn toàn bộ đối tượng đó.
Trong phần này, chúng ta sẽ thực hiện giải bài toán 0/1 Knapsack Problem bằng cách sử dụng Dynamic Programming.
Giả sử bạn có các đối tượng với trọng lượng và giá trị như sau:
Chiếc ba lô có sức chứa tối đa là 5 đơn vị trọng lượng.
Giải thuật Dynamic Programming sẽ sử dụng một bảng hai chiều, trong đó:
Chúng ta sẽ tính toán giá trị tối đa có thể đạt được cho từng trọng lượng của ba lô và từng đối tượng, dựa trên việc chọn hoặc không chọn đối tượng đó.
Dưới đây là đoạn mã PHP để giải quyết bài toán xếp ba lô 0/1:
<?php
// Hàm giải quyết bài toán 0/1 Knapsack
function knapsack($capacity, $weights, $values, $n) {
// Tạo bảng DP hai chiều
$K = array();
// Khởi tạo bảng với giá trị 0
for ($i = 0; $i <= $n; $i++) {
for ($w = 0; $w <= $capacity; $w++) {
if ($i == 0 || $w == 0) {
$K[$i][$w] = 0;
} else if ($weights[$i - 1] <= $w) {
// Tính giá trị tối ưu khi chọn hoặc không chọn đối tượng
$K[$i][$w] = max($values[$i - 1] + $K[$i - 1][$w - $weights[$i - 1]], $K[$i - 1][$w]);
} else {
$K[$i][$w] = $K[$i - 1][$w];
}
}
}
// Trả về giá trị lớn nhất có thể bỏ vào ba lô
return $K[$n][$capacity];
}
// Các đối tượng với trọng lượng và giá trị
$values = array(3, 4, 5, 8);
$weights = array(2, 3, 4, 5);
$capacity = 5;
$n = count($values);
// Gọi hàm và hiển thị kết quả
echo "Giá trị lớn nhất có thể bỏ vào ba lô: " . knapsack($capacity, $weights, $values, $n);
?>
$capacity: Sức chứa của ba lô.$weights: Mảng chứa trọng lượng của các đối tượng.$values: Mảng chứa giá trị của các đối tượng.$n: Số lượng đối tượng.$K): Là bảng hai chiều để lưu trữ giá trị tối ưu cho từng đối tượng và từng trọng lượng ba lô.
$K[$n][$capacity].Khi chạy đoạn mã trên, kết quả sẽ là:
Giá trị lớn nhất có thể bỏ vào ba lô: 8
Điều này có nghĩa rằng, với sức chứa tối đa là 5, giá trị lớn nhất có thể chọn từ các đối tượng là 8, tương ứng với đối tượng có trọng lượng 5 và giá trị 8.
Bài toán xếp ba lô (Knapsack Problem) là một bài toán tối ưu hóa nổi tiếng, thường được giải quyết bằng cách sử dụng phương pháp lập trình động (Dynamic Programming). Với giải thuật này, chúng ta có thể tìm ra cách chọn đối tượng để đạt giá trị lớn nhất mà vẫn đảm bảo không vượt quá sức chứa của ba lô. Bài toán này có nhiều ứng dụng trong thực tế như tối ưu hóa việc phân bổ tài nguyên, lập kế hoạch sản xuất, hoặc trong các trò chơi chiến thuật.
Bài toán xếp ba lô (Knapsack Problem) không chỉ là một thử thách toán học mà còn có nhiều ứng dụng thực tế trong cuộc sống, từ tối ưu hóa nguồn lực đến lập kế hoạch sản xuất. Thông qua việc giải quyết bài toán này bằng PHP và sử dụng kỹ thuật lập trình động, chúng ta có thể xây dựng các giải pháp tối ưu hóa hiệu quả. Hiểu sâu về bài toán và các kỹ thuật giải sẽ giúp bạn áp dụng nó vào nhiều lĩnh vực khác nhau trong lập trình và tối ưu hóa hệ thống.
