QUY HOẠCH ĐỘNG Các bài toán quy hoạch động chiếm một vị trí khá quan trọng trong tổ chức hoạt động và sản xuất. Chính vì lẽ đó mà trong các kì thi học sinh giỏi quốc gia và quốc tế chúng ta thường gặp loại toán này. Thông thường những bạn nào dùng phương pháp quay lui, vét cạn cho các bài toán quy hoạch động thì chỉ có thể vét được các tập dữ liệu nhỏ, kích thước chừng vài chục byte. . | Sáng tạo trong Thuật toán và Lập trình Tập I 191 CHƯƠNG 7 QUY HOẠCH ĐỘNG Các bài toán quy hoạch động chiếm một vị trí khá quan trọng trong tổ chức hoạt động và sản xuất. Chính vì lẽ đó mà trong các kì thi học sinh giỏi quốc gia và quốc tế chúng ta thường gặp loại toán này. Thông thường những bạn nào dùng phương pháp quay lui vét cạn cho các bài toán quy hoạch động thì chỉ có thể vét được các tập dữ liệu nhỏ kích thước chừng vài chục byte. Nếu tìm được đúng hệ thức thể hiện bản chất quy hoạch động của bài toán và khéo tổ chức dữ liệu thì ta có thể xử lí được những tập dữ liệu khá lớn. Có thể tóm lược nguyên lí quy hoạch động do Bellman phát biểu như sau Quy hoạch động Quy hoạch động là lớp các bài toán mà quyết định ở bước thứ i phụ thuộc vào quyết định ở các bước đã xử lí trước hoặc sau đó. Để giải các bài toán quy hoạch động ta có thể theo sơ đồ sau đây Sơ đồ giải bài toán quy hoạch động 1. Lập hệ thức Lập hệ thức biểu diễn tương quan quyết định của bước đang xử lí với các bước đã xử lí trước đó. Khi đã có hệ thức tương quan chúng ta đã có thể xây dựng ngay thuật giải tuy nhiên các hệ thức này thường là các biểu thức đệ quy do đó dễ gây ra hiện tượng tràn miền nhớ khi ta tổ chức chương trình trực tiếp bằng đệ quy. 2. Tổ chức dữ liệu và chương trình Tổ chức dữ liệu tính toán dần theo từng bước. Nên tìm cách khử đệ quy. Trong các bài toán quy hoạch động thuộc chương trình phổ thông thường đòi hỏi một vài mảng hai chiều. 3. Làm tốt Làm tốt thuật toán bằng cách thu gọn hệ thức quy hoạch động và giảm kích thước miền nhớ. Bài . Chia thưởng Cần chia hết m phần thưởng cho n học sinh sắp theo thứ tự từ giỏi trở xuống sao cho mồi bạn không nhận ít phần thưởng hơn bạn xếp sau mình. 1 m n 70. Hãy tính số cách chia. Thí dụ với số phần thưởng m 7 và số học sinh n 4 sẽ có 11 cách chia 7 phần thưởng cho 4 học sinh theo yêu cầu của đầu bài. Đó là Sáng tạo trong Thuật toán và Lập trình Tập I 192 Phương án 1 7 0 0 0 2 6 1 0 0 3 5 2 0 0 4 5 1 1 0 5 4 3 0 0 6 4 2 1 0 7 3 3 1 0 8 3
