Nếu thử tất cả cách chọn đồ vật → sẽ có 2^n cách =>độ phức tạp hàm mũ=>không khả thi khi n lớnTa giải quyết theo hướng quy hoạch động
Khi xét đến đồ vật thứ i, với sức chứa còn lại là j thì giá trị lớn nhất có thể đạt được là bao nhiêu?
⟹ Đặt: dp[i][j]: giá trị lớn nhất khi xét i đồ vật đầu tiên, ba lô chứa tối đa j. Và đương nhiên: Khi chưa chọn đồ nào → giá trị dp[i][j]= 0
Với mỗi đồ vật i, có 2 lựa chọn:
=> ta phải so sánh 2 cách để lấy tốt nhất (cách có giá trị lớn hơn mà lại nhẹ hơn)
Đi ngược từ dp[n][W] về (0, 0)