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
n Đã lùi lại sửa đổi của 14.183.134.100 (Thảo luận) quay về phiên bản cuối của Én bạc AWB |
|||
Dòng 46:
Với mỗi loại, có thể chọn một phần của nó (ví dụ: 1Kg bơ có thể được cắt ra thành nhiều phần để bỏ vào ba lô)
▲Bài toán xếp ba lô có thể được giải trong [[thời gian giả-đa thức]] bằng [[quy hoạch động]]. Dưới đây là lời giải quy hoạch động cho ''bài toán xếp ba lô không bị chặ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''. Khi đó, với mỗi ''i'' ≤ ''C'', đặt ''A''(''i'') là giá trị lớn nhất có thể đạt được với tổng chi phí không vượt quá ''i''. Rõ ràng, ''A''(''C'') là đáp số của bài toán.
Hàng 64 ⟶ 62:
''A''(''i'',''j'') được định nghĩa đệ quy như sau:
* ''A''(0, ''j'') = 0 f[i][j]:= giá trị lớn nhất có thể lấy được; v[i]:= là giá trị của đồ vật thứ i ; w[i]:=trọng lượng của đồ vật thứ i; NOTES: Đây là bài toán không giới hạn đồ vật
* ''A''(''i'', 0) = 0
* ''A''(''i'', ''j'') = ''A''(''i'' - 1, ''j'') if c<sub>i</sub> > ''j''
* ''A''(''i'', ''j'') = max(''A''(''i'' - 1, ''j''), v<sub>i</sub> + ''A''(''i'' - 1, ''j'' - c<sub>i</sub>)) if c<sub>i</sub> ≤ ''j f[i][j]=max(f[i-1][j],v[i]+f[i][j-w[i]]) // khi đã lấy vật thứ i thì có thể lấy thêm nữa nên ta có f[i][j-w[i]]:= đã trừ đi trọng lượng của đồ vật thứ i // i là đồ vật không giới hạn''
Để có lời giải, ta tính A(''n'', ''C''). Để làm điều này, ta có thể dùng 1 bảng để lưu các tính toán trước đó. Cách giải này do đó sẽ chạy trong thời gian O(''nC'') và không gian O(''nC''), tuy ta có thể giảm độ phức tạp không gian xuống O(''C'') bằng một số sửa đổi nhỏ.
| |||