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 replaced: ; → ;, ==External links== → ==Liên kết ngoài== using AWB |
|||
Dòng 65:
* 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
Dòng 72:
* ''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''
Để 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ỏ.
Dòng 95:
* <cite name="Martello">{{cite book | title = Knapsack problems: Algorithms and computer implementations | last1=Martello|first1=Silvano|last2=Toth|first2=Paolo| publisher =Wiley-Interscience | year = 1990 | isbn = 0-471-92420-2|mr=1086874 }}</cite>
==Liên kết ngoài==
*[http://www.or.deis.unibo.it/knapsack.html Free download of the book "Knapsack problems: Algorithms and computer implementations", by Silvano Martello and Paolo Toth]
*[http://www.cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming.pdf Lecture slides on the knapsack problem]
Dòng 106:
*[http://www.adaptivebox.net/CILib/code/qkpcodes_link.html Codes for Quadratic Knapsack Problem]
{{Use dmy dates|date=September 2010}}
[[Thể loại:Mật mã học]]
[[Thể loại:Bài toán NP-đầy đủ]]
| |||