Bài toán cái ba lô
Bài học 7 trên 15 trong khóa học Nhập môn quy hoạch động của Coddy.
Bài toán cái túi là một bài toán tối ưu kinh điển trong khoa học máy tính. Đề bài rất đơn giản: cho một tập hợp các vật phẩm, mỗi vật phẩm có khối lượng và giá trị, hãy xác định những vật phẩm cần đưa vào một bộ sưu tập sao cho tổng khối lượng nhỏ hơn hoặc bằng giới hạn cho trước và tổng giá trị đạt mức tối đa.
Có hai dạng bài toán cái túi:
- Bài toán cái túi 0/1: Ở dạng này, kẻ trộm không thể lấy một phần của vật phẩm, họ chỉ có thể lấy toàn bộ hoặc bỏ lại.
- Bài toán cái túi phân số: Ở dạng này, kẻ trộm có thể lấy một phần của vật phẩm, tức là có thể lấy một phần trong vật phẩm đó.
Thử thách
Trung bìnhViết một hàm tên là knapsack để giải bài toán ba lô 0/1. Hàm nhận ba đầu vào:
- Một danh sách trọng lượng của n món đồ (w1, w2, ... , wn).
- Một danh sách giá trị của n món đồ (v1, v2, ... , vn).
- Sức chứa trọng lượng tối đa của ba lô (W).
Sau đó, hàm sẽ đưa ra giá trị tối đa có thể đạt được khi xếp đồ vào ba lô.
Ví dụ:
weights = [10, 20, 30]
values = [60, 100, 120]
W = 50
knapsack(weights, values, W)Đầu ra:
220 # taking the 2 largest itemsTự làm thử
def knapsack(wrights, values, W):
# Viết code tại đâyTất cả bài học trong Nhập môn quy hoạch động
1Giới thiệu về quy hoạch động
Quy hoạch động là gì?Vì sao quy hoạch động quan trọng?Ứng dụng trong nhiều lĩnh vực3Thuật toán quy hoạch động
Dãy con chung dài nhấtBài toán cái ba lôBài toán đổi tiềnKhoảng cách chỉnh sửaTự luyện tập: Trình biên dịch Python online