Quy hoach dong

Quy hoạch động

Bài tập 1 Cái túi(cơ bản, cần nhớ)
Cho N đồ vật có thể tích, và giá trị xác định(N<=100). Người ta có 1 cái túi có thể tích là V(V<=200). Tìm cách lấy các đồ vật sao cho thể tích của chúng ko vượt quá V, và giá trị là lớn nhất có thể.
Thuật toán
Gọi F(i,j) là giá trị lớn nhất khi có i đồ vật, và tổng thể tích các đồ vật cần lấy không vượt quá j.
F(i,j) = max(F(i-1,j), F(i-1, j-Vi))
Với dk : j >= Vi

Bài tập 2 Phân tích tổng(cơ bản)
Cho N số nguyên dương (N<=100), và 1 số M (M<=50000). Tìm cách phân tích M thành tổng của N số đã cho, mỗi số sử dụng không quá 1 lần.

Procedure QHD;
Var
Danhdau : array [1..max] of integer;
Gh,i,j,k : integer;
Begin
Fillchar(danhdau, sizeof(danhdau), 0);
Danhdau[0]:=n+1;
Gh : =0;
For I : =1 to n do
Begin
For j:=0 to gh do {gh la gia tri }
If (danhdau[j] <>i) and (danhdau[j] > 0) then{neu chua co gia tri tai j hoac vi tri day khac I danhdau[j]=0 khi khong or co tong nao co gia tri =j}
Begin
K:=j+so[i];{tang j them so dang xet}
If danhdau[k]=0 then
Danhdau[k]:=i; {bo xung so j+so dang xet vao mang}
End;
Inc(gh, so[i]); {cong them vao gh so i}
End;
End;

Bài tập 3 Hình chữ nhật lớn nhất
Lưới hình chữ nhật kích thước MxN(M,n<=100), gồm các số nguyên thuộc [-127..127].
Nhiệm vụ của bạn là tìm 1 hình chữ nhật mà tổng các số trong đó là lớn nhất
Thuật toán
Gọi F(i,j,k) là giá trị lớn nhất của hình chữ nhật cần tìm khi hình chữ nhật đó bị giới hạn bởi 2 cột i,j, và đáy của nó nằm trên dòng k.
F(i,j,k) = max(f(i,j,k-1) + tong(i,j,k), tong(i,j,k))
Trong đó hàm tong(i,j,k) có nhiệm vụ tính tổng các ô ở dòng k, bị giới hạn bởi 2 cột i,j.

Bài tập 4 (Quốc gia 1999) Trạm xăng
Có N trạm xăng (N<=200) đánh số từ 1 đến N. Vị trí của cây xăng thứ i là di (d1 < d2 < ... < dn).
Cần đặt k bề chứa xăng tại k trong số n cây xăng sao cho khoảng cách lớn nhất từ cây xăng không có bể chứa xăng đến cây xăng có bể chứa xăng gần nó nhất là nhỏ nhất
Thuật toán :
Gọi F(i,j) là khoảng cách Min khi có i cây xăng, j bể chứa.
F(i,j) = Min (Max (F(t,j-1), F1(t,i)))
Với t>=j-1
F1(t,j) là cách đặt tối ưu khi có 1 bể chứa, từ các cây xăng t đến cây xăng j. Để tính hàm này, ta duyệt các cây xăng cần đặt.

Bài tập 5 (IOI 99) : Vùng đất
Cho ma trận M x N. Tìm 1 hình chữ