tailieunhanh - bài giảng các chuyên đề phần 6

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á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[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. | Quy hoạch động 12 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á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 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 2 giá 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ở 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 . đến khi tính hết dòng n. 01 M 0 1 2 0 0 0 0 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ấ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 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ếp F 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. Bài toán cái túi program The_Bag const max 100 var W V Array of Integer F array 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 Lê Minh Hoàng Quy hoạch động 13 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