Trong lĩnh vực tối ưu hoá, việc giải quyết các bài toán liên quan đến việc chọn làm sao để tận dụng được tốt nhất các tài nguyên có hạn là vô cùng quan trọng. Một trong những bài toán phổ biến thuộc loại này là bài toán Cái Balo (Knapsack Problem). Trong bài viết này, chúng ta sẽ xem xét cách cài đặt thuật toán Fractional Knapsack Problem trong lập trình.
Tổng quan về bài toán Hem phẩn số
Bài toán này tập trung vào việc chọn lựa một tập hợp các đối tượng có trọng lượng và giá trị khác nhau để tối ưu hoá giá trị tổng cộng của cái balo, trong khi không vượt quá giới hạn trọng lượng đã định trước. Khác với bài toán Knapsack thông thường, ở đây chúng ta có thể chọn một phần của đối tượng (fractional), tức là có thể chia nhỏ đối tượng đó để đạt được giá trị tối ưu nhất.
Đầu vào và yêu cầu
- Một danh sách các đối tượng, mỗi đối tượng có trọng lượng và giá trị tương ứng.
- Khối lượng tối đa mà balo có thể chứa.
Quy trình giải quyết
- Tính tỉ lệ giá trị trên trọng lượng (value-to-weight ratio) cho mỗi đối tượng.
- Sắp xếp các đối tượng theo tỉ lệ này từ cao đến thấp.
- Chọn các đối tượng để đưa vào balo theo thứ tự đã sắp xếp, nếu không đủ trọng lượng để chứa toàn bộ đối tượng, chỉ chọn phần nhỏ tương ứng.
Cài đặt trong Python
Dưới đây là một ví dụ về cách cài đặt thuật toán này trong Python:
class Item:
def __init__(self, value, weight):
self.value = value
self.weight = weight
self.ratio = value / weight
def fractional_knapsack(items, max_weight):
# Sắp xếp các đối tượng theo tỉ lệ giá trị/trọng lượng
items.sort(key=lambda x: x.ratio, reverse=True)
total_value = 0.0 # Tổng giá trị có trong balo
for item in items:
if max_weight == 0:
break
if item.weight <= max_weight:
# Nếu trọng lượng của đối tượng nhỏ hơn hoặc bằng khả năng còn lại của balo
max_weight -= item.weight
total_value += item.value
else:
# Nếu trọng lượng của đối tượng lớn hơn khả năng còn lại của balo
fraction = max_weight / item.weight
total_value += item.value * fraction
max_weight = 0
return total_value
# Ví dụ về dữ liệu đầu vào
items = [Item(60, 10), Item(100, 20), Item(120, 30)]
max_weight = 50
# Chạy thuật toán
max_value = fractional_knapsack(items, max_weight)
print("Giá trị tối đa có thể chứa trong balo:", max_value)
Giải thích mô tả thuật toán
- Item Class: Định nghĩa một đối tượng Item với giá trị (value), trọng lượng (weight) và tỉ lệ giá trị trên trọng lượng (ratio).
- Sorting: Sắp xếp danh sách các đối tượng theo tỉ lệ.
- Greedy Approach: Lọc qua các đối tượng, thêm chúng vào balo theo thứ tự từ cao đến thấp của tỉ lệ giá trị trên trọng lượng cho đến khi gặp phải giới hạn trọng lượng của balo.
Mở rộng và ứng dụng
Thuật toán này có thể được mở rộng và ứng dụng trong nhiều bài toán khác nhau liên quan đến việc phân bổ tài nguyên, tối ưu hóa lộ trình và nhiều lĩnh vực khác. Việc hiểu biết và áp dụng thuật toán Fractional Knapsack không chỉ giúp tối ưu hóa giải pháp mà còn giúp việc lập trình trở nên hiệu quả và linh hoạt hơn.
Hy vọng bài viết đã cung cấp một cái nhìn toàn diện về cách cài đặt thuật toán Fractional Knapsack cũng như các bước tư duy để giải quyết vấn đề tối ưu hóa này.
Comments