Đề tài Bài toán đổi tiền (Quy hoạch động)

Trong quá trình học tập, chúng ta gặp rất nhiều các bài tập về Toán-Tin. Các bài tập dạng này rất phong phú và đa dạng. Thực tế chưa có thuật toán hoàn chỉnh có thể áp dụng cho mọi bài toán. Tuy nhiên người ta đã tìm ra một số thuật toán chung như chia để trị, tham ăn, quay lui,. Các thuật toán này có thể áp dụng để giải một lớp khá rộng các bài toán hay gặp trong thực tế. Trong bài viết này, tôi muốn đề cập với các bạn một thuật toán khác, đó là thuật toán quy hoạch động. Ý tưởng cơ bản của thuật toán là: Để giải một bài toán ta chia bài toán đó thành các bài toán nhỏ hơn để giải một cách dễ dàng. Sau đó kết hợp lời giải các bài toán con, ta có được lời giải bài toán ban đầu. Trong quá trình giải các bài toán con đôi khi ta gặp rất nhiều kết quả trùng lặp của các bài toán con. Để tăng tính hiệu quả, thay vì phải tính lại các kết quả đó, ta lưu chúng vào một bảng. Khi cần lời giải của một bài toán con nào đó ta chỉ cần truy tìm trong bảng, không cần tính lại. Ý tưởng của thuật toán quy hoạch động khá đơn giản nhưng khi áp dụng thuật toán vào trường hợp cụ thể lại không dễ dàng (điều này cũng tương tự như nguyên tắc Dirichlet trong toán vậy). Khi giải bài toán bằng phương pháp này, chúng ta phải thực hiện hai yêu cầu quan trọng sau: - Tìm công thức truy hồi xác định nghiệm bài toán qua nghiệm các bài toán con nhỏ hơn. - Với mỗi bài toán cụ thể, ta đề ra phương án lưu trữ nghiệm một cách hợp lý để từ đó có thể truy tìm nhanh nhất.

TÀI LIỆU LUẬN VĂN CÙNG DANH MỤC

HỖ TRỢ TÌM VÀ TẢI TÀI LIỆU

  • Từ ngày 01/05/2022

    Luanvan365 sẽ có thêm dịch vụ hỗ trợ các bạn tìm kiếm các tài liệu, luận văn ở nhiều website khác nhau
    Bạn có thể liên hệ với Admin để được hỗ trợ nhé
  • THÔNG TIN LIÊN HỆ


    Phone: 0909.773687 (Zalo, Text) Facebook : Facebook chat hỗ trợ

  • XEM THÊM THÔNG TIN

    Xem thêm bài viết
LIÊN HỆ NGAY

TIN KHUYẾN MÃI

  • thư viện luận văn

    Thư viện tài liệu Phong Phú

    Hỗ trợ download nhiều Website

  • thư viện luận văn

    Nạp thẻ & Download nhanh

    Hỗ trợ nạp thẻ qua Momo & Zalo Pay

  • thư viện luận văn

    Nhận nhiều khuyến mãi

    Khi đăng ký & nạp thẻ ngay Hôm Nay

NẠP THẺ NGAY