Quy hoạch động bài toán Cái túi 0/1 tối ưu không gian

Mục tiêu kiến thức

• Hiểu sâu cấu trúc con tối ưu và phương trình trạng thái của bài toán Cái túi 0/1 (0/1 Knapsack).
• Nâng cấp tối ưu hóa không gian bộ nhớ từ bảng 2 chiều O(N × C) xuống mảng 1 chiều O(C) bằng cách duyệt ngược dung lượng.
• Phân tích độ phức tạp thời gian O(N × C) và không gian O(C).

Mô tả bài toán

Máy chủ huấn luyện đồ họa AI của AI Empire Academy có tổng dung lượng bộ nhớ VRAM là C GB (1 ≤ C ≤ 10⁴). Có N mô hình AI mã nguồn mở đang được xem xét để nạp vào bộ nhớ (1 ≤ N ≤ 1000).

Mô hình thứ i cần chiếm một lượng bộ nhớ là W_i GB và mang lại giá trị hiệu năng tính toán là V_i điểm (1 ≤ W_i ≤ C, 1 ≤ V_i ≤ 10⁹). Do tính chất độc lập, mỗi mô hình chỉ có thể được chọn tối đa một lần (0 hoặc 1).

Hãy tìm tổng giá trị hiệu năng lớn nhất có thể đạt được sao cho tổng dung lượng VRAM của các mô hình được chọn không vượt quá C.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ N ≤ 1000.
• 1 ≤ C ≤ 10⁴.
• 1 ≤ W_i ≤ C.
• 1 ≤ V_i ≤ 10⁹.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.