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...
Nội dung trích xuất từ tài liệu:
bài giảng các chuyên đề phần 6Quy 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 0gồ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. 0 1 ... M 0 0 0 0 0 1 2 ... ... n4. 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 khichọ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ọngó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ủabả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; {Nhập dữ liệu từ thiết bị nhập chuẩn (Input)}procedure Enter;var i: Integer;begin ReadLn(n, M); for i := 1 to n do ReadLn(W[i], V[i]);end; {Tính bảng phương án bằng công thức truy hồi}procedure Optimize;var i, j: Integer;begin {Điền cơ sở quy hoạch động} FillChar(F[0], SizeOf(F[0]), 0); for i := 1 to n do for j := 0 to M do {Tính F[i, j]} beginLê Minh HoàngQuy hoạch động 13 {Giả sử không chọn gói thứ i thì F[i, j] = F[i - 1, j]} 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; {Truy vết tìm nghiệm tối ưu}procedure Trace;begin WriteLn(F[n, M]); {In ra giá trị lớn nhất có thể kiếm được} {Truy vết trên bảng phương án từ hàng n lên hàng 0} while n 0 do begin {Nếu có chọn gói thứ n} if F[n, M] F[n - 1, M] then begin Write(n, ); M := M - W[n]; {Đã 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;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(Output);end.III. BIẾN ĐỔI XÂUCho xâu ký tự X, xét 3 phép biến đổi:a) Insert(i, C): i là số, C là ký tự: Phép Insert chèn ký tự C vào sau vị trí i của xâu X.b) Replace(i, C): i là số, C là ký tự: Phép Replace thay ký tự tại vị trí i của xâu X bởi ký tự C.c) Delete(i): i là số, Phép Delete xoá ký tự tại vị trí i của xâu X.Yêu cầu: Cho trước xâu Y, hãy tìm một số ít nhất các phép biến đổi trên để biến xâu X thành xâu Y.Input: file văn bản STR.INP• Dòng 1: Chứa xâu X (độ dài ≤ 100)• Dòng 2: Chứa xâu Y (độ dài ≤ 100)Output: file văn bản STR.OUT ghi các phép biến đổi cần thực hiện và xâu X tại mỗi phép biến đổi. STR.INP STR.OUT PBBCEFATZ 7 QABCDABEFA PBBCEFATZ -> Delete(9) -> PBBCEFAT PBBCEFAT -> Delete(8) -> PBBCEFA PBBCEFA -> Insert(4, B) -> PBBCBEFA PBBCBEFA -> Insert(4, A) -> PBBCABEFA PBBCABEFA -> Insert(4, D) -> PBBCDABEFA PBBCDABEFA -> Replace(2, A) -> PABCDABEFA PABCDABEFA -> Replace(1, Q) -> ...