- Quy hoạch động. - Ý tưởng quy hoạch động 2. - Bài toán đoạn con lớn nhất. - Bài toán dãy con chung dài nhất. - Bài toán đếm số dãy con có tổng cho trước 5. - Bài toán xếp ba lô. - Phân tích về quy hoạch động 7. - Ý tưởng quy hoạch động. - Top-down vs Bottom-up. - Top-down. - Bottom-up. - Top-down:. - Chia bài toán lớn thành các bài toán nhỏ. - Bottom-up:. - Giải bài toán nhỏ trước. - Tổ hợp các lời giải nhỏ thành lời giải của bài toán lớn. - Quy hoạch động:. - Thường dùng cho các bài toán tối ưu. - Nguyên tắc: lời giải tối ưu của bài toán lớn sử dụng kết quả tối ưu của bài toán con. - tìm đoạn con (dãy con liên tiếp) trong A có tổng các phần tử là lớn nhất. - Quy hoạch động: tính giá trị S k sử dụng kết quả tính S k-1. - Dãy con = dãy được lập ra từ dãy cha bằng cách chọn lấy một số phần tử, giữ nguyên thứ tự. - Dãy con chung của A và B: là dãy con của cả A và B. - Cần tìm: dãy con có nhiều phần tử nhất (dài nhất). - Hàm S(p, q) trả về độ dài của dãy con chung dài nhất của A p = (a 1 , a 2. - Top-down: tính từ S(m, n) trở đi, chia nhỏ dần bài toán. - Sử dụng bộ nhớ để lưu lại các giá trị đã tính toán. - Bài toán đếm số dãy con có tổng cho trước. - Đếm số dãy con có tổng cho trước. - Bài của buổi trước, giờ hãy thử giải nó bằng kĩ thuật quy hoạch động. - Hãy đếm xem có bao nhiêu dãy con của A có tổng các phần tử đúng bằng S. - Kết quả: 3 dãy. - số dãy con của A có tổng đúng bằng S. - Dãy con không chứa a n. - Đếm số dãy con của A = (a 1 , a 2. - a n-2 , a n-1 ) có tổng bằng S. - Dãy con có chứa a n. - a n-2 , a n-1 ) có tổng bằng S-a n. - Sử dụng bộ nhớ để lưu lại các kết quả đã tính toán. - Bài toán cái túi, knapsack problem,.... - Hãy chọn ra một số đồ vật có tổng trọng lượng tối đa là W và có tổng giá trị lớn nhất.. - Ở phương án tối ưu của f(k, h) có 2 tình huống xảy ra:. - Có sử dụng độ vật thứ k*: f(k, h. - Không sử dụng độ vật thứ k: f(k, h. - Bottom-up: tính từ dưới lên. - Phân tích về quy hoạch động. - Tóm lược về quy hoạch động. - Phương án tối ưu của bài toán lớn dựa trên kết quả tối ưu của từng bài toán con. - Sử dụng bộ nhớ để lưu lại kết quả tính toán, tránh phải tính lại. - Top-down: đệ quy có nhớ, tính từ bài toán lớn giảm dần xuống. - Bottom-up: vòng lặp, tính từ bài toán nhỏ tăng dần lên. - Thường có 2 loại bài toán:. - Bài toán đếm (tìm số lượng cấu hình). - Bài toán tối ưu (tìm cấu hình min, max, max của min, min của max,...). - Ưu điểm của quy hoạch động. - Nhược điểm của quy hoạch động. - Hầu hết các vấn đề giải được bằng quy hoạch động là bài giải bằng chia để trị. - Nhưng không phải bài chia để trị nào cũng giải được bằng quy hoạch động. - Nếu số bài toán con tăng quá nhanh, quy hoạch động sẽ không khả thi. - Đòi hỏi mọi bài toán con phải được giải tối ưu. - Hãy tìm dãy con không giảm dài nhất của A.. - Dãy con mà phần tử đứng sau không bé hơn phần tử đứng trước. - Nhiều phần tử nhất
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt