Thuật toán quy hoạch tối ưu

Quy hoạch tối ưu và đề quy hoạch lui

Đào Đức Minh

Có lẽ các bạn đã rất quen thuộc với thuật toán quy hoạch động và kĩ thuật đệ quy-quay lui

đã được giới thiệu qua nhiều bài viết trên tạp chí ISM. Nếu chúng ta kết hợp hai tư tưởng

trên thì sẽ được một lớp bài toán khá thú vị,có nội dung như sau: yêu cầu tìm tất cả các

trường hợp để được kết quả tối ưu.

I. Bài toán 1:

Cho N đồ vật,đồ vật thứ i có một khối lượng là mi. Có 1 ba lô chịu được khối lượng tối đa

là M. Hãy tìm tất cả các cách chọn một số đồ vật nào đó bỏ vào ba lô sao cho tổng khối

lượng các đồ vật được chọn là lớn nhất nhưng không vượt quá M.

Giải thuật:

Ta dễ dàng nhận ra đây là bài toán ba lô quen thuộc, được giải quyết bằng thuật toán quy

hoạch động. Tuy nhiên, ta cần tìm tất cả các cách chọn để được kết quả tối ưu nhất. Vì vậy,

ta cũng sử dụng kĩ thuật đệ quy-quay lui để tìm tất cả các trường hợp.

Như vậy,thuật toán như sau:

+ Bước 1: Ăp dụng thuật toán quy hoạch động tìm giá trị W lớn nhất có thể bỏ vào ba lô từ

các đồ vật đã cho.

+ Bước 2: Ăp dụng kĩ thuật đệ quy-quay lui tìm tất cả các trường hợp chọn đồ vật để có

tổng giá trị là W. Mỗi trường hợp là một cách chọn cần tìm.

II. Bài toán 2:

Cho một ma trận (M x N) có M dòng và N cột ,trong ma trận có thể có một số ô không

được đi vào và đánh dấu '#', những ô được đi vào đánh dấu '*'. Hãy tìm tất cả các đường đi

ngắn nhất để đi từ ô (M1,N1) đến ô (M2,N2).

Bắt đầu từ ô (M1,N1).

Đường đi miêu tả bằng dãy gồm các chữ số:'0' có nghĩa là đến ô bên trái ô đang đứng;'1'-

lên ô phía trên;'2' - đến ô bên phải và '3' - xuống ô phía dưới.

Các bước đi thực hiện từ trái sang phải của dãy số.

Dữ liệu vào: