Thuật toán quy hoạch động

Giải thuật quy hoạch động

CongHiep_87@yahoọcom

Đối với các bạn yêu thích môn lập trình thì có lẽ giải thuật qui hoạch động tương đối quen

thuộc trong việc giải quyết các vấn đề tin học. Tuy nhiên, sẽ thật là khó để có thể tìm được

cơ cở và công thức cho việc sử dụng qui hoạch động. Chính vì vấn đề này, qui hoach động

lại trở thành không phổ biến. Đối với những bài toán như vậy, chúng ta lại cố gắng đi tìm

cách giải khác ví dụ như vét cạn hay tham lam....điều đó thật là dở! Chính vì vậy, tôi muốn

đưa ra một số bài toán áp dụng qui hoạch động để mong rằng sau bài báo này, các bạn sẽ

yêu thích giải thuật này hơn.

Trước hết các bạn phải luôn nhớ rằng, giải thuật qui hoạch động được xuất phát từ nguyên

lí Bellman: nếu 1 cấu hình là tối ưu thì mọi cấu hình con của nó cũng là tối ưu. Chính vì

vậy để xây dựng 1 cấu hình tối ưu, ta hãy xây dựng dần các cấu hình con sao cho các cấu

hình con này cũng phải tối ưu Đây chính là đường lối chủ đạo cho mọi bài toán qui hoạch

động. Sau đây là một số bài toán được giải quyết bằng qui hoạch động.

I. Các bài toán

Bài 1: Trước tiên chúng ta hãy xét 1 bài toán thật đơn giản và quen thuộc đó là tìm giá trị

lớn nhất trong n số là a1, a2, ..., an. Giải quyết bài toán này, ta sẽ xây dựng các cấu hình con

tối ưu bằng cách lần lượt tìm số lớn nhất trong k số đầu tiên với k chạy từ 1 đến n:

K=1: max1:=a1;

K=2: max2:=max(max1,a2);

K=3: max3:=max(max2,a3);

..............................................

K=n: maxn:=max(maxn-1,an);

Như vậy khi k đạt tới n thì maxn chính là giá trị lớn nhất trong n số đã chọ Việc cài đặt

chương trình hết sức đơn giản như sau:

Uses crt;

Var a: array[1..100] of integer;

n,k,max: integer;

Begin

Write('Cho so luong phan tu: ');readln(n);

For i:=1 to n do begin write('a[',i,']= ');readln(a[i]);end;

Max:=a[1];

For k:=2 to n do

If a[k]>max then max:=a[k];

Write('Gia tri lon nhat cua day cac so da cho la: ',max);

Readln

End.

Bây giờ chúng ta xét đến bài toán 2 có phần hấp dẫn hơn. Đây chính là một trong những

bài toán điển hình cho giải thuật qui hoạch động:

Bài 2: Bài toán cái túi: Cho n loại đồ vật (1≤n≤100) với một đồ vật loại thứ i (1≤i≤n) có

trọng lượng là a[i] và giá trị sử dụng là c[i]. Một nhà thám hiểm cần mang theo một số đồ

vật vào túi của mình sao cho tổng trọng lượng các đồ vật đem theo không vượt quá sức