Bài toán xếp ba lô

Bài toán xếp ba lô (một số sách ghi là bài toán cái túi, tương tự như bài toán xếp vali) là một bài toán tối ưu hóa tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Một số cách phát biểu nội dung bài toán: Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ...
Nội dung trích xuất từ tài liệu:
Bài toán xếp ba lô Bài toán xếp ba lôBài toán xếp ba lô (một số sách ghi là bài toán cái túi, tương tự như bài toán xếpvali) là một bài toán tối ưu hóa tổ hợp. Bài toán được đặt tên từ vấn đề chọn nhữnggì quan trọng có thể nhét vừa vào trong một cái túi (với giới hạn khối lượng) đểmang theo trong một chuyến đi.Một số cách phát biểu nội dung bài toán:Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng vàgiá trị khác nhau, nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượngtối đa là M. Vậy kẻ trộm nên bỏ vào ba lô những món nào và số lượng bao nhiêuđể đạt giá trị cao nhất trong khả năng mà hắn có thể mang đi được.Một hành khách chỉ được mang theo một vali có khối lượng hàng hoá tối đa làM. Hành khách đó đã chuẩn bị ra N dồ vật được đánh số từ 1 đến N để chuẩn bịmang theo. Đồ vật thứ i có trọng lượng là ai và giá trị sử dụng là ci (i = 1, 2, ..N) Yêu cầu: Chỉ ra đồ vật mà hành khách đó cần mang theo sao cho tổng giá trị sửdụng là lớn nhất?Bài toán:Trong siêu thị có n gói hàng (n ≤ 100), gói hàng thứ i có trọng lượng là Wi ≤ 100và trị giá Vi ≤ 100. Một tên trộm đột nhập vào siêu thị, tên trộm mang theo một cáitúi có thể mang được tối đa trọng lượng M ( M ≤ 100). Hỏi tên trộm sẽ lấy đinhững gói hàng nào để được tổng giá trị lớn nhất.Input: file văn bản BAG.INP• Dòng 1: Chứa hai số n, M cách nhau ít nhất một dấu cách• n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương Wi, Vi cách nhau ít nhấtmột dấu cáchOutput: file văn bản BAG.OUT• Dòng 1: Ghi giá trị lớn nhất tên trộm có thể lấy• Dòng 2: Ghi chỉ số những gói bị lấyBAG.INP BAG.OUT5 11 1133 52144549 1044Cách giải:Nếu gọi F[i, j] là giá trị lớn nhất có thể có bằng cách chọn trong các gói {1, 2, …,i} với giới hạn trọng lượng j. Thì giá trị lớn nhất khi được chọn trong số n gói vớigiới hạn trọng lượng M chính là F[n, M].1. Công thức truy hồi tính F[i, j].Với giới hạn trọng lượng j, việc chọn tối ưu trong số các gói {1, 2, …,i – 1, i} đểcó giá trị lớn nhất sẽ có hai khả năng:• Nếu không chọn gói thứ i thì F[i, j] là giá trị lớn nhất có thể bằng cách chọn trongsố các gói {1, 2, …, i – 1} với giới hạn trọng lượng là j. Tức là F[i, j] = F[i - 1, j]• Nếu có chọn gói thứ i (tất nhiên chỉ xét tới trường hợp này khi mà Wi ≤ j) thì F[i,j] bằng giá trị gói thứ i là Vi cộng với giá trị lớn nhất có thể có được bằng cáchchọn trong số các gói {1, 2, …, i – 1} với giới hạn trọng lượng j – Wi. Tức là vềmặt giá trị thu được: F[i, j] = Vi + F[i - 1, j - Wi]Vì theo cách xây dựng F[i, j] là giá trị lớn nhất có thể, nên F[i, j] sẽ là max trong 2giá trị thu được ở trên.2. Cơ sở quy hoạch động:Dễ thấy F[0, j] = giá trị lớn nhất có thể bằng cách chọn trong số 0 gói = 0.3. Tính bảng phương án:Bảng phương án F gồm n + 1 dòng, M + 1 cột, trước tiên được điền cơ sở quyhoạch động: Dòng 0 gồm toàn số 0. Sử dụng công thức truy hồi, dùng dòng 0 tínhdòng 1, dùng dòng 1 tính dòng 2, v.v… đến khi tính hết dòng n.4. Truy vết:Tính xong bảng phương án thì ta quan tâm đến F[n, M] đó chính là giá trị lớn nhấtthu được khi chọn trong cả n gói với giới hạn trọng lượng M. Nếu F[n, M] = F[n -1, M] thì tức là không chọn gói thứ n, ta truy tiếp F[n - 1, M]. Còn nếu F[n, M] ≠F[n - 1, M] thì ta thông báo rằng phép chọn tối ưu có chọn gói thứ n và truy tiếpF[n - 1, M - Wn]. Cứ tiếp tục cho tới khi truy lên tới hàng 0 của bảng phương án.PROG03_2.PAS * Bài toán cái túiprogram The_Bag;const max = 100;var W, V: Array[1..max] of Integer; F: array[0..max, 0..max] of Integer; n, M: Integer;procedure Enter; {Nhập dữ liệu từ thiết bị nhập chuẩn (Input)}var i: Integer;begin ReadLn(n, M); for i := 1 to n do ReadLn(W[i], V[i]);end;procedure Optimize; {Tính bảng phương án bằng công thức truy hồi}var i, j: Integer;begin FillChar(F[0], SizeOf(F[0]), 0); {Điền cơ sở quy hoạch động} for i := 1 to n do for j := 0 to M do begin {Tính F[i, j]} F[i, j] := F[i - 1, j]; {Giả sử không chọn gói thứ i thì F[i, j] = F[i - 1, j]} {Sau đó đánh giá: nếu chọn gói thứ i sẽ được lợi hơn thì đặt lại F[i, j]} if (j >= W[i]) and (F[i, j] < F[i - 1, j - W[i]] + V[i]) then F[i, j] := F[i - 1, j - W[i]] + V[i]; end;end;procedure Trace; {Truy vết tìm nghiệm tối ưu}begin WriteLn(F[n, M]); {In ra giá trị lớn nhất có thể kiếm được} while n 0 do {Truy vết trên bảng phương án từ hàng n lên hàng 0} begin if F[n, M] F[n - 1, M] then {Nếu có chọn gói thứ n} begin Write(n, ); M := M - W[n]; {Đã chọn gói thứ n rồi thì chỉ có thể mang thêm được trọnglượng M - Wn nữa thôi} end; Dec(n); end;end;begin {Định nghĩa lại thiết bị nhập/xuất chuẩn} Assign(Input, BAG.INP); Reset(Input); Assign(Output, BAG.OUT); Rewrite(Output); Enter; Optimize; Trace; Close(Input); Close(Outp ...