Trong siêu thị có n gói hàng (n i iDòng 1: Chứa hai số n, M cách nhau ít nhất một dấu cáchn dòng tiếp theo, dòng thứ i chứa hai số nguyên dương Wi, Vi cách nhau ít nhất mộ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ấyDòng 2: Ghi chỉ số những gói bị lấy
BAG.INP
BAG.OUT
5
11
11
3
3
5 2 1
4
4
5
4
9
10
4
4
Cách giải:
Nếu gọi F 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ới giới hạn trọng lượng M chính là F.
Bạn đang xem: Hướng dẫn giải bài toán cái túi
Bạn đang xem: Hướng dẫn giải bài toán cái túi
3.2.1. Công thức truy hồi tính F.
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 là giá trị lớn nhất có thể bằng cách chọn trong số các gói {1, 2, …, i – 1} với giới hạn trọng lượng là j, tức là F = FNế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 i cộng với giá trị lớn nhất có thể có được bằng cách chọ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 = Vi + F
Vì theo cách xây dựng F là giá trị lớn nhất có thể, nên F sẽ là max trong 2 giá trị thu được ở trên.
Xem thêm: Học Phí Đại Học Công Nghiệp Thực Phẩm Tp Hcm Học Phí, Học Phí Trường Đại Học Công Nghiệp Thực Phẩm Tp
3.2.2.Cơ sở quy hoạch động:
3.2.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ở quy hoạ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ính dòng 1, dùng dòng 1 tính dòng 2, v.v… đến khi tính hết dòng n.
3.2.4. Truy vết:
Tính xong bảng phương án thì ta quan tâm đến F đó chính là giá trị lớn nhất thu được khi chọn trong cả n gói với giới hạn trọng lượng M. Nếu F = F thì tức là không chọn gói thứ n, ta truy tiếp F. Còn nếu F ¹ F 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ếp F. Cứ tiếp tục cho tới khi truy lên tới hàng 0 của bảng phương án.
P_3_03_3.PAS * Bài toán cái túi
program The_Bag;const InputFile = ‘BAG.INP’; OutputFile = ‘BAG.OUT’; max = 100;var W, V: Array of Integer; F: array of Integer; n, M: Integer;procedure Enter; var i: Integer; fi: Text; begin Assign(fi, InputFile); Reset(fi); ReadLn(fi, n, M); for i := 1 to n do ReadLn(fi, W, V); Close(fi); 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, SizeOf(F), 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} F := F; {Giả sử không chọn gói thứ i thì F = F} {Sau đó đánh giá: nếu chọn gói thứ i sẽ được lợi hơn thì đặt lại F} if (j >= W) and (F F> + V) then F := F> + V; end; end;procedure Trace; {Truy vết tìm nghiệm tối ưu} var fo: Text; begin Assign(fo, OutputFile); Rewrite(fo); WriteLn(fo, F); {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 F then {Nếu có chọn gói thứ n} begin Write(fo, n, ‘ ‘); M := M – W; {Đã chọn gói thứ n rồi thì chỉ có thể mang thêm được trọng lượng M – Wn nữa thôi} end; Dec(n); end; Close(fo); end;begin Enter; Optimize; Trace;end.Chuyên mục: Kiến thức thú vị
- Cách bán vé máy bay online hiệu quả
- Cách thử kem dưỡng da có chì
- Cách xóa chi tiết thừa trong photoshop cs6
- Công thức tính khoảng cách từ một điểm đến một đường thẳng
