Chào các bạn. Hôm nay, mình xin giới thiệu với các bạn sơ lược về bài toán Subset sum. Để giới thiệu đầy đủ sẽ rất dài và vượt quá khả năng của mình, chắc phải nhờ các bạn chuyên ngành khoa học máy tính, do vậy mình chỉ giới thiệu sơ lược và nêu ứng dụng để giải bài toán trong thực tế. Bài toán như sau: cho mảng n số nguyên dương a(1 to n) và số k, hãy xác định tồn tại hay không một tập con của a có tổng bằng k, tìm 1 bộ số nếu có? Một ứng dụng thường gặp đối với các bạn làm sổ sách số liệu (hình như các bác kế toán gọi là "bốc thuốc"): sếp chi một khoản tiền k đồng mà lý do không thể đưa vào sổ sách được, các bác kế toán sẽ tách ra thành các nội dung chi hợp lý có tổng = k (các nội dung này nằm trong danh mục có sẵn được chi của công ty và có chi phí cụ thể, đây chính là mảng a(1 to n)).
Ví dụ a=[2, 5, 9, 20, 30] , k =35, tồn tại bộ số [5, 30] có tổng bằng k.
(Còn tiếp...)
Ví dụ a=[2, 5, 9, 20, 30] , k =35, tồn tại bộ số [5, 30] có tổng bằng k.
(Còn tiếp...)