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 |
/* Cách giải bằng quy hoạch độngBà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… |
||
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ô)
== Cách giải bằng quy hoạch
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.
| |||