Balo 1

1. Mô hình
 Cho n vật, vật i nặng ai và có giá trị bi. Hãy chọn ra một số vật để cho vào balô sao cho tổng khối lượng không vượt quá W và tổng giá trị là lớn nhất. Chú ý rằng mỗi vật có thể được chọn nhiều lần.

2. Công thức 
Gọi L(i, j ) là tổng giá trị lớn nhất khi được chọn i vật từ 1 đến i cho vào balô với tổng khối
lượng không vượt quá j. L( n, W) sẽ là đáp số của bài toán (là giá trị lớn nhất có được nếu chọn n vật và tổng khối lượng không vượt quá W). Công thức tính L(i,t) như sau: Trang 8 • L(i,0) = 0; L(0,j)=0. • L(i,j) = L(i,j) nếu t < ai.
• L(i,t)=max( L (i-1,j), L(i,j–ai)+bi) nếu t  ≥ ai. Trong đó: L(i–1,j) là giá trị có được nếu không đưa vật i vào balô, L(i,j–ai)+bi là giá trị có được nếu chọn vật i.

3. Cài đặt
Ta có thể dùng một mảng 2 chiều để lưu bảng phương án, tuy nhiên dựa trên nhận xét rằng để
tính dòng i của bảng phương án chỉ cần dòng i–1, ta chỉ cần dùng 2 mảng một chiều P và L có chỉ số từ 0 đến m để lưu 2 dòng đó. Đoạn chương trình con tính bảng phương án như sau.
L[t] := 0; {với mọi t}
for i := 1 to n do begin
P:=L;
for t := 0 to m do
if t<a[i] then L[t]:=P[t]
else L[t] := max(P[t],P[t–a[i]]);
end; 
Nếu để ý kĩ bạn sẽ thấy rằng đoạn trình trên chỉ viết giống công thức QHĐ chứ chưa tối ưu. Chẳng hạn đã có lệnh gán P:=L, sau đó lại có gán L[t]:=P[t] với các giá trị t<a[i] là không cần thiết. Bạn đọc có thể tự cải tiến để chương trình tối ưu hơn. Chi phí không gian của cách cài đặt trên là O(m) và chi phí thời gian là O(n.m).