Mặt nạ bit
Bài học 13 trên 15 trong khóa học Nhập môn quy hoạch động của Coddy.
Bit masking là một kỹ thuật trong quy hoạch động, giúp tối ưu hóa lời giải cho các bài toán liên quan đến tập con hoặc tổ hợp các phần tử. Kỹ thuật này biểu diễn mỗi tập con hoặc tổ hợp dưới dạng mặt nạ bit, trong đó mỗi bit biểu thị sự có mặt hoặc vắng mặt của một phần tử tương ứng. Bằng cách sử dụng các thao tác trên bit, thuật toán quy hoạch động có thể duyệt hiệu quả tất cả các tập con hoặc tổ hợp có thể có mà không cần tạo chúng một cách tường minh.
Thử thách
KhóĐếm các tập con có tổng cho trước
Trong thử thách này, bạn được cho một mảng số nguyên và một tổng mục tiêu. Nhiệm vụ của bạn là tìm số tập con có tổng bằng tổng mục tiêu. Bạn có thể dùng mặt nạ bit để duyệt qua tất cả các tập con có thể có của mảng và đếm số tập con có tổng bằng tổng mục tiêu.
Tự làm thử
def count_subsets(arr, target_sum):
# Viết code ở đâ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