Bài giảng Thuật toán ứng dụng: Quy hoạch động. Chương này cung cấp cho học viên những nội dung về: tổng quan chia để trị; dãy con cực đại; dãy con tăng dần dài nhất; dãy con chung dài nhất; . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | THUẬT TOÁN ỨNG DỤNG QUY HOẠCH ĐỘNG Phạm Quang Dũng Bộ môn KHMT dungpq@ 1 NộI dung Tổng quan chia để trị Dãy con cực đại Dãy con tăng dần dài nhất 2 Quy hoạch động Sơ đồ chung Chia bài toán xuất phát thành các bài toán con không nhất thiết độc lập với nhau Giải các bài toán con từ nhỏ đến lớn lời giải được lưu trữ lại vào 1 bảng Bài toán con nhỏ nhất phải được giải 1 cách trực tiếp Xây dựng lời giải của bài toán lớn hơn từ lời giải đã có của các bài toán con nhỏ hơn truy hồi Số lượng bài toán con cần được bị chặn bởi đa thức của kích thước dữ liệu đầu vào Phù hợp để giải hiệu quả một số bài toán tối ưu tổ hợp 3 Bài toán dãy con cực đại Cho dãy số nguyên a a1 a2 aN. Hãy tìm dãy con bao gồm các phần tử liên tiếp của dãy a có tổng lớn nhất 4 Bài toán dãy con cực đại Phân chia Ký hiệu Pi là bài toán tìm dãy con bao gồm các phần tử liên tiếp có tổng cực đại mà phần tử cuối cùng là ai với mọi i 1 n Ký hiệu Si là tổng các phần tử của lời giải của Pi i 1 n S1 a1 Si Si -1 ai nếu Si-1 gt 0 ai nếu Si-1 0 Tổng các phần tử của dãy con cực đại của bài toán xuất phát là max S1 S2 Sn 5 Bài toán dãy con cực đại maxsubseq a1 a2 . . . aN s 1 a 1 res s 1 for i 2 N do if s i-1 gt 0 then s i s i-1 a i else s i a i if s i gt res then res s i return res 6 Bài toán dãy con tăng dần dài nhất Cho dãy số nguyên a a1 a2 aN. Hãy tìm dãy con tăng dần bao gồm các phần tử không nhất thiết liên tiếp nhau của dãy a có số phần tử lớn nhất 7 Bài toán dãy con tăng dần dài nhất Ký hiệu Pi là bài toán tìm dãy con cực đại mà phần tử cuối cùng là ai với mọi i 1 n Ký hiệu Si là số phần tử của lời giải của Pi i 1 n S1 1 Si max 1 max Sj 1 j lt i aj lt ai Số phần tử của dãy con cực đại của bài toán xuất phát là max S1 S2 Sn 8 Bài toán dãy con tăng dần dài nhất incsubseq a1 a2 . . . aN s 1 1 res s 1 for i 2 N do s i 1 for j 1 i-1 do if a j lt a i then if s i lt s j 1 then s i s j 1 if s i gt res then res s i return res 9 Dãy con chung dài nhất Ký hiệu X X1 X2 Xn một dãy con của X là dãy được .
