Hướng dẫn giải của Đếm Tập Con Thỏa Hai Ràng Buộc Tổng
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Định nghĩa DP 2 chiều
Đặt ~dp[w][v]~ = số tập con (các phần tử đã xét) có tổng trọng lượng ~w~ và tổng giá trị ~v~.
Khởi tạo: ~dp[0][0] = 1~.
Công thức chuyển trạng thái
Với mỗi đồ vật ~(w_i, v_i)~, duyệt ~w~ từ ~W~ xuống ~w_i~, ~v~ từ ~V~ xuống ~v_i~: $$dp[w][v] = dp[w][v] + dp[w-w_i][v-v_i] \pmod{10^9+7}$$
Duyệt ngược cả hai chiều để đảm bảo 0/1 Knapsack.
Kết quả
~dp[W][V]~ sau khi xử lý tất cả đồ vật.
Phân tích độ phức tạp
- Thời gian: ~O(N \times W \times V)~ với ~N=50, W=V=500~: ~50 \times 500 \times 500 = 12{,}500{,}000~.
- Bộ nhớ: ~O(W \times V)~ = ~500 \times 500 = 250{,}000~ ô nhớ.
Tổng quát hóa
Đây là dạng tổng quát của Knapsack nhiều ràng buộc. Với ~D~ chiều ràng buộc, độ phức tạp là ~O(N \times \prod_{d=1}^{D} C_d)~.
Bình luận