Quy hoạch động bài toán Cái ba lô 0/1

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

• Hiểu công thức truy hồi quy hoạch động bài toán Cái ba lô 0/1:

DP[i][w] = max(DP[i-1][w], DP[i-1][w - weight[i]] + value[i])

• Kỹ thuật tối ưu hóa không gian bộ nhớ từ bảng 2D O(N × W) xuống mảng 1D O(W) bằng cách duyệt ngược từ capacity về weight.
• Xử lý ngoại lệ ValueError khi dung lượng sức chứa âm.

Mô tả bài toán

Hệ thống quản lý VRAM tại AI Empire Academy cần nạp các mô hình AI vào bộ nhớ card đồ họa GPU có dung lượng giới hạn capacity (tính bằng MB). Mỗi mô hình thứ i chiếm dung lượng weights[i] và đem lại giá trị điểm chất lượng values[i]. Mỗi mô hình chỉ được chọn tối đa đúng một lần (0 hoặc 1).

Hãy viết hàm knapsack_01(weights: list[int], values: list[int], capacity: int) -> int tính tổng giá trị lớn nhất có thể đạt được mà tổng trọng lượng không vượt quá capacity.

Quy tắc bắt lỗi:

• Nếu capacity < 0, hàm phải ném ra ngoại lệ ValueError("Suc chua khong the am").
• Nếu danh sách rỗng hoặc capacity == 0, trả về 0.

Ràng buộc

• 0 ≤ len(weights) == len(values) ≤ 200.
• 1 ≤ weights[i], values[i] ≤ 10⁴.
• -10⁴ ≤ capacity ≤ 2000.
• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.