<p>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ớn<br><i><strong>Ta giải quyết theo hướng quy hoạch động</strong></i></p><h3>B1. Xây dựng trạng thái</h3><p>Khi xét đến đồ vật thứ i, với sức chứa còn lại là j thì <strong>giá trị lớn nhất có thể đạt được là bao nhiêu?</strong></p><p>⟹ Đặt: dp[i][j]: giá trị lớn nhất khi xét <strong>i đồ vật đầu tiên</strong>, ba lô chứa tối đa <strong>j. Và đương nhiên: Khi chưa chọn đồ nào → giá trị dp[i][j]= 0</strong></p><h3>B2. Quyết định chọn i hay không</h3><p>Với mỗi đồ vật i, có 2 lựa chọn:</p><ol><li><strong>Không chọn đồ vật i</strong><ul><li>giữ nguyên kết quả trước đó</li></ul></li><li><strong>Chọn đồ vật i (nếu thoả mãn (đủ chỗ): j >= w[i])</strong><ul><li>cộng thêm giá trị vi của đồ vật i</li></ul></li></ol><p> => 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)</p><h3>B3. Kết quả: dp[n][W]</h3><p> </p><h3>B4. Lấy danh sách đồ vật được chọn</h3><p>Đi ngược từ dp[n][W] về (0, 0)</p><ul><li>Nếu: dp[i][j] != dp[i-1][j] thì <strong>đã chọn đồ vật i</strong></li><li>Sau đó: j = j - w[i]</li></ul>