Hướng dẫn học quy hoạch động và một số bài toán quy hoạch động điển hình



Lý thuyết đồ thị:#LýThuyếtĐồThịHoàng Gia
Quy hoạch động:#Quy_Hoạch_Động_HG
Hướng dẫn học quy hoạch động và một số bài toán quy hoạch động điển hình
Phương pháp quy hoạch động là dùng để giải bài toán tối ưu có bản chất đệ quy, tức là việc tìm phương án tối ưu cho bài toán ban đầu có thể đưa về tìm phương án tối ưu của một số hữu hạn các bài toán con.
Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất (bài toán cơ sở) để từ đó từng bước giải quyết nhưng bài toán lớn hơn, cho tới khi giải được bài toán lớn nhất (bài toán ban đầu).

Bài toán giải theo phương pháp quy hoạch động gọi là bài toán quy hoạch động.
Công thức phối hợp nghiệm của các bài toán con để có nghiệm của bài toán lớn gọi là công thức truy hồi của quy hoạch động.
Tập các bài toán có ngay lời giải để từ đó giải quyết các bài toán lớn hơn gọi là cơ sở quy hoạch động.
Không gian lưu trữ lời giải các bài toán con gọi là bảng phương án (bảng phương án dùng mảng 1 chiều hoặc 2 chiều để lưu trữ kết quả của bài toán con) của quy hoạch động.
1. Giới thiệu Quy hoạch động:
Link:
2. Tổng dãy con trong đoạn [p..q]:
Link:
Input:
Program:
3. Dãy con trong đoạn [p..q] tổng Mod k=0:
Link:
Input:
Program:
4. Dãy con đơn điệu dài nhất:
Link:
Input:
Program:
5. Xâu con chung dài nhất:
Link:
Input:
Program:
6. Tìm dãy con liên tiếp dài nhất

Nguồn: https://lexuanquang.org/

Xem thêm bài viết khác: https://lexuanquang.org/cong-nghe/

5 thoughts on “Hướng dẫn học quy hoạch động và một số bài toán quy hoạch động điển hình

Leave a Reply

Your email address will not be published. Required fields are marked *