Khác biệt giữa bản sửa đổi của “Bài toán xếp ba lô”
Nội dung được xóa Nội dung được thêm vào
Không có tóm lược sửa đổi |
|||
Dòng 55:
Ở đây, giá trị lớn nhất của tập rỗng được lấy bằng 0. Tính dần các kết quả từ ''A''(0) tới ''A''(''C''), ta sẽ được lời giải. Do việc tính mỗi ''A''(''i'') đòi hỏi xem xét ''n'' đồ vật (tất cả các giá trị này đã được tính từ trước), và có ''C'' giá trị của các ''A''(''i'') cần tính, nên thời gian chạy của lời giải quy hoạch động là O(''nC'').
Điều này không mâu thuẫn với thực tế rằng bài toán xếp ba lô là [[NP-đầy đủ]], do ''C'', không như ''n'', không thuộc mức đa thức theo độ dài của đầu vào cho bài toán. Độ dài đầu vào bài toán tỉ lệ
Một giải pháp quy hoạch động tương tự cho ''bài toán xếp ba lô 0-1'' cũng chạy trong [[thời gian giả-đa thức]]. Cũng như trên, gọi các chi phí là ''c<sub>1</sub>'', ..., ''c<sub>n</sub>'' và các giá trị tương ứng là ''v<sub>1</sub>'', ..., ''v<sub>n</sub>''. Ta cần cực đại hóa tổng giá trị với điều kiện tổng chi phí không vượt quá ''C''. Định nghĩa một hàm đệ quy ''A''(''i'', ''j'') là giá trị lớn nhất có thể đạt được với chi phí không vượt quá ''j'' và sử dụng các đồ vật trong khoảng từ ''x''<sub>1</sub> tới ''x<sub>i</sub>''.
| |||