Tóm tắt đề bài

Cho ~n~ đồ vật, đồ vật thứ ~i~ có giá trị là ~f_i~ và giá mua là ~s_i~, mỗi đồ vật chỉ có số lượng là ~1~. Bạn có ~m~ đồng để mua các đồ vật, và bạn cần mua các đồ vật sao cho tổng giá trị là lớn nhất, mà tổng giá mua ~\le m~.

Tuy vậy, có ~k~ ràng buộc dạng ~(a, b)~ có nghĩa: nếu bạn mua vật ~a~ thì phải mua vật ~b~. ~k~ ràng buộc này không tạo thành chu trình.

Giới hạn: ~n \le 50~, ~f_i, s_i, m \le 1000~.

Lời giải

Bài toán này là bài toán thuộc NP-hard, vì vậy không có lời giải chính xác trong thời gian đa thức. Dưới đây chỉ là cách mình dựa vào để sinh test.

Với ~n \le 25~

Với giới hạn này, ta hoàn toàn có thể duyệt mọi tập con của ~n~ phần tử. Sau đó, ta cần kiểm tra tập con này có thỏa mãn không.

Trước hết, ta cần kiểm tra tập con này có thỏa mãn ~k~ điều kiện nói trên không. Có thể duyệt đủ ~k~ điều kiện, tuy nhiên điều này là khá chậm. Ta có thể làm cách khác:

• Với mỗi điều kiện ~i~, ta sẽ lưu các vật phẩm phải mua nếu mua vật phẩm thứ ~i~ dưới dạng bitmask.
• Sau đó, ta có thể dễ dàng kiểm tra bằng phép toán AND hai tập hợp. Gọi ~mask~ là tập con của ~n~ phần tử ta đang thử, ~must~ là tập các vật phẩm phải mua khi mua vật phẩm ~i~ (mà vật phẩm ~i~ cũng phải nằm trong ~mask~), thì tập này thỏa mãn nếu ~mask~ ~\&~ ~must = must~.

Sau đó, ta cần tính tổng số tiền phải trả cho tập con này, nếu ~\le m~ thì ta cập nhật vào kết quả.

Độ phức tạp: ~O~ ~(2^n \times n)~, hằng số thấp do phép ~\&~ khá nhanh.

Một số cách nhánh cận:

• Nếu tập ta đang duyệt, có tổng giá trị nhỏ hơn kết quả ta tìm thấy hiện tại, ta bỏ qua.
• Chỉ cần vi phạm một trong ~k~ điều kiện, ta sẽ ~break~ sớm.

Với ~n \le 50~

Đến đây có thể có một số cách như:

• Meet in the middle (độ phức tạp sẽ có dạng ~2^x + 3^y~ với ~x + y = n~). Ta sẽ chia ~n~ thành hai tập ~x~ và ~y~ một cách tối ưu nhất.
• DP bitmask và lưu khéo các trạng thái.
• Tham lam, chẳng hạn theo tỷ lệ ~\frac {f_i}{s_i}~.
• Leo đồi (hill climbing).
• Luyện kim mô phỏng (simulated annealing), nâng cấp từ leo đồi.
• Tối ưu cục bộ (local search).
• if test.

Do điều kiện chỉ cần sinh test, mình đã để thời gian chạy cho mỗi test case từ ~5 - 7~ phút để cho ra kết quả tối ưu nhất, đồng thời bỏ qua các test có thuật giải đúng.