C bài toán cái túi bằng quay lui

Cần chọn các vật này đặt vào một chiếc túi xách có giới hạn trọng lượng m, sao cho tổng giá trị sử dụng các vật được chọn là lớn nhất.

Phân tích và thiết kế thuật toán :

Bài toán chiếc túi xách chuyển về bài toán sau :

Cho nên ta sẽ kết hợp đánh giá nhánh cận trong quá trình liệt kê các lời giải theo phương pháp quay lui.

Mô hình ban đầu có thể sử dụng như sau :

Try(i)

for(j = 1 -> t)

if(Chấp nhận được)

{

Xác định xi theo j;

Ghi nhận trạng thái mới;

if(i==n)

Cập nhật lời giải tối ưu;

else

{

Xác định cận trên g;

if( g(x1,..., xi) <= f*)

Try(i+1);

}

Trả lại trạng thái cũ cho bài toán;

}

o Cách chọn vật :

Ta chọn vật theo đơn giá giảm dần.

Không mất tính tỏng quát, ta giả sử các loại vật cho theo thứ tự giảm dần của đơn giá.

o Đánh giá cận trên :

Giả sử đã tìm được lời giải bộ phận : (x1,…,xi)

Khi đó :

- Giá trị của túi xách thu được :

- Tương ứng với trọng lượng các vật đã được xếp vào chiếc túi :

- Do đó, giới hạn trọng lượng của chiếc túi còn lại là :

Ta thấy đây là một bài toán tìm max. Danh sách các đồ vật được sắp xếp theo thứ tự giảm của đơn giá để xét phân nhánh. 1. Nút gốc biểu diễn cho trạng thái ban đầu của ba lô, ở đó ta chưa chọn một vật nào. Tổng giá trị (TGT) được chọn TGT=0. Cận trên của nút gốc CT = W * Đơn giá lớn nhất. 2. Nút gốc sẽ có các nút con tương ứng với các khả năng chọn đồ vật có đơn giá lớn nhất. Với mỗi nút con ta tính lại các thông số: · TGT = TGT (cũ) + số đồ vật được chọn * giá trị mỗi vật. · W = W (cũ) - số đồ vật được chọn * trọng lượng mỗi vật. · CT = TGT + W (mới) * Đơn giá của vật sẽ xét kế tiếp.

3. Trong các nút con, ta sẽ ưu tiên phân nhánh cho nút con nào có cận trên lớn hơn trước. Các con của nút này tương ứng với các khả năng chọn đồ vật có đơn giá lớn tiếp theo. Với mỗi nút ta lại phải xác định lại các thông số TGT, W, CT theo công thức đã nói trong bước 2. 4. Lặp lại bước 3 với chú ý: đối với những nút có cận trên nhỏ hơn hoặc bằng giá lớn nhất tạm thời của một phương án đã được tìm thấy thì ta không cần phân nhánh cho nút đó nữa. 5. Nếu tất cả các nút đều đã được phân nhánh hoặc bị cắt bỏ thì phương án có giá lớn nhất là phương án cần tìm. Ví dụ : Với bài toán cái ba lô đã cho, sau khi tính đơn giá cho các đồ vật và sắp xếp các đồ vật theo thứ tự giảm dần của đơn giá ta được bảng sau.

Gọi x1, x2, x3, x4 là số lượng cần chọn tương ứng của các đồ vật b, a, d, c. Nút gốc A biểu diễn cho trạng thái ta chưa chọn bất cứ một đồ vật nào. Khi đó tổng giá trị TGT =0, trọng lượng của ba lô W=37 (theo đề ra) và cận trên CT = 37*2.5 = 92.5, trong đó 37 là W, 2.5 là đơn giá của đồ vật b. Với đồ vật b, ta có 4 khả năng: chọn 3 đồ vật b (X1=3), chọn 2 đồ vật b (X1=2), chọn 1 đồ vật b (X1=1) và không chọn đồ vật b (X1=0). Ứng với 4 khả năng này, ta phân nhánh cho nút gốc A thành 4 con B, C, D và E. Với nút con B, ta có TGT = 0+ 3*25 = 75, trong đó 3 là số vật b được chọn, 25 là giá trị của mỗi đồ vật b. W = 37- 3*10 = 7, trong đó 37 là trọnh lượng ban đầu của ba lô, 3 là số vật b được, 10 là trọng lượng mõi đồ vật b. CT = 75 + 7*2 = 89, trong đó 75 là TGT, 7 là trọng lượng còn lại của ba lô và 2 là đơn giá của đồ vật a. Tương tự ta tính được các thông số cho các nút C, D và E, trong đó cận trên tương ứng là 84, 79 và 74. Trong các nút B, C, D và E thì nút B có cận trên lớn nhất nên ta sẽ phân nhánh cho nút B trước với hy vọng sẽ có được phương án tốt từ hướng này. Từ nút B ta chỉ có một nút con F duy nhất ứng với X2=0 (do trọng lượng còn lại của ba lô là 7, trong khi trọng lượng của mỗi đồ vật a là 15). Sau khi xác định các thông số cho nút F ta có cận trên của F là 85.5. Ta tiếp tục phân nhánh cho nút F. Nút F có 2 con G và H tương ứng với X3=1 và X3=0. Sau khi xác định các thông số cho hai nút này ta thấy cận trên của G là 84 và của H là 82 nên ta tiếp tục phân nhánh cho nút G. Nút G có hai con là I và J tương ứng với X4=1 và X4=0. Đây là hai nút lá (biểu diễn cho phương án) vì với mỗi nút thì số các đồ vật đã được chọn xong. Trong đó nút I biểu diễn cho phương án chọn X1=3, X2=0, X3=1 và X4=1 với giá 83, trong khi nút J biểu diễn cho phương án chọn X1=3, X2=0, X3=1 và X4=01 với giá 81. Như vậy giá lớn nhất tạm thời ở đây là 83. Quay lui lên nút H, ta thấy cận trên của H là 82<83 nên cắt tỉa nút H. Quay lui lên nút C, ta thấy cận trên của C là 84>83 nên tiếp tục phân nhánh cho nút C. Nút C có hai con là K và L ứng với X2=1 và X2=0. Sau khi tính các thông số cho K và L ta thấy ận trên của K là 83 và của L là 75.25. Cả hai giá trị này đều không lớn hơn 83 nên cả hai nút này đều bị cắt tỉa. Cuối cùng các nút D và E cũng bị cắt tỉa. Như vậy tất cả các nút trên cây đều đã được phân nhánh hoặc bị cắt tỉa nên phương án tốt nhất tạm thời là phương án cần tìm. Theo đó ta cần chọn 3 đồ vật loại b, 1 đồ vật loại d và một đồ vật loại c với tổng giá trị là 83, tổng trọng lượng là 36.