Như vậy, Fk(y) là giá trị lớn nhất của hàm mục tiêu khi các đồ vật được chọn từ k loại đầu tiên và túi chỉ chứa hạn chế tới y (kg). – Khi k = 1 thì công thức () trên đây trở thành: F1(y) = Max{c1x1 : x1 = 0, 1, , [y/a1]} = c1[y/a1], y = 0, b . – ∀ k = 2,n , () được viết dưới dạng: k −1 ⎧ k ⎫ Fk(y) = Max ⎨∑ c j x j : ∑ a j x j ≤ y − ak xk , víi x j. | Fk y Max -z k I j 1 CJXJ zajXj y Xj 0 vj 1 k j 1 Như vậy Fk y là giá trị lớn nhất của hàm mục tiêu khi các đồ vật được chọn từ k loại đầu tiên và túi chỉ chứa hạn chế tới y kg . - Khi k 1 thì công thức trên đây trở thành F1 y Max C1X1 X1 0 1 . y ai Ci y ai y 0 b . - v k 2 n được viết dưới dạng Fk y Max k k -1 __ - z cJXj z aJxj y- akxk với XJ 0 vj 1 k . j 1 j 1 Max 1 ckxk Max 1 z cJxj z aJxj y xk k akxk với Xj 0 vj 1 k -1 Max 1 ckxk Max - z cjXj z ajXj y k-Jk akxk với Xj 0 vj 1 k -1 trong đó Jk 0 1 . . y ak . Vậy ta có phương trình truy toán sau v k 1 n Fk y Max ckxk Fk -i y - akxk với Jk 0 1 . y ak . xk-Jk Kết luận. Thực hiện lần lượt các công thức và với k 0 n vy 0 b chúng ta sẽ tìm được phương án tối ưu cho bài toán cái túi. Chúng ta sẽ tiến hành giải lại ví dụ 5 bằng phương pháp vừa nêu trên. Có thể nhận thấy rằng các bảng thiết lập sau đây là khá giống với các bảng trong mục . Giai đoạn 1 Coi F0 y 0 vy 0 b và tính F1 y . y y a1 F1 y c1 y a1 x1 tối ưu 0 0 0 0 1 0 0 0 2 0 0 0 3 1 8 1 4 1 8 1 5 1 8 1 6 2 16 2 7 2 16 2 8 2 16 2 9 3 24 3 10 3 24 3 11 3 24 3 12 4 32 4 13 4 32 4 96 Giai đoạn 2 Tính F2 y y X2 0 . y a2 F2 y Max c2x2 F1 y a2x2 x2 tối ưu 0 0 0 0 1 0 0 0 2 1 0 5 1 3 1 0 8 0 4 2 1 0 10 2 5 2 1 0 13 1 6 3 2 1 0 16 0 7 3 2 1 0 18 2 8 4 3 2 1 0 21 1 9 4 3 2 1 0 24 0 10 5 4 3 2 1 0 26 2 11 5 4 3 2 1 0 29 1 12 6 5 4 3 2 1 0 32 0 13 6 5 4 3 2 1 0 34 2 Giai đoạn 3 y x3 0 1 . y a3 F3 y Max c3x3 F2 y a3X3 x3 tối ưu 0 0 0 0 1 1 0 1 1 2 2 1 0 5 0 3 3 2 1 0 8 0 4 4 3 2 1 0 10 0 5 5 4 3 2 1 0 13 0 6 6 5 4 3 2 1 0 16 0 7 7 6 5 4 3 2 1 0 18 0 8 8 7 6 5 4 3 2 1 0 21 0 9 9 8 7 6 5 4 3 2 1 0 24 0 10 10 9 8 7 6 5 4 3 2 1 0 26 0 11 11 10 9 8 7 6 5 4 3 2 1 0 29 0 12 12 11 10 9 8 7 6 5 4 3 2 1 0 32 0 13 13 12 11 10 9 8 7 6 5 4 3 2 1 0 34 0 97 Sau khi hoàn thành giai đoạn 3 để tìm phương án tối ưu của bài toán chúng ta làm như sau Căn cứ bảng giai đoạn 3 thì zmax Max F3 y3 34 ứng với y3 13 và x3 0. Lại căn cứ bảng giai đoạn 2 thì y2 y3 - a3x3 13 - 1x0
