Bài toán cái túi
Võ Khắc Huấn
Bài toán: Cho một tập hữu hạn U = {ui; i =1..n} mỗi phần tử ui U có kích cỡ S(ui) và số tự nhiênB.
Liệucó một tập con U' U sao cho S(ui)= B. Trong đó: uiU'.
Đểminh hoạ cho bài toán, chúng ta lấy ví dụ sau: giả sử tập u có 4 phần tử {u1,u2, u3, u4}, kích cỡ lần lượt là S(u1)= 1, S(u2) = 5, S(u3) = 2, S(u4 ) = 3 và B = 3.Bạn dễ dàng thấy rằng có hai phương án:
+ U1' = {u1, u3}vì S(u1)+ S(u3) = 3
+ U2' = {u4}vì S (u4 ) = 3
Đôikhi, tập U' được biểu diễn như là dãy có thứ tự các số nhị phân, phần tử là 1 -nếu nó thuộc U', hoặc 0 - nếu ngược lại là không thuộc. Như ví dụ trên ta có:
+ U1' = {u1, u3}(1, 0, 1, 0)
+ U2' = {u4} (0, 0, 0, 1)
Knapsackthuộc lớp bài toán NPC (không đa thức). Nghĩa là, nói chung không có thuật toánhữu hiệu nào để giải nó cho trường hợp bất kỳ. Điều này không có nghĩa là tấtcả các trường hợp đều có cùng độ phức tạp. Chúng ta phát biểu lại bài toán dướidạng có thể giải được bằng thuật toán có thời gian tuyến tính. Và gọi nó là bàitoán Knapsack dễ.
Bài toán EKN:Cho n đồ vật, có khối lượng lần lượt là S1, S2,..., Snsao cho:
vàmột cái ba lô có sức chứa B.
Câuhỏi đặt ra là liệu có cách nào để bỏ vào ba lô một số vật để tổng khối lượngcủa chúng bằng B? Chúng ta minh hoạ bằng hai phương pháp sau:
Chon = 6, B = 45
Và
Bâygiờ, chúng ta tìm một phương án V= (V1 , V2 ,..., V6 ).Trong đó Vi = 1 nếu vật thứ i được bỏ vào ba lô, Vi = 0ngược lại vật bị để ngoài.
Chúngta thấy:
V6 = 1, B - S6 = 45 - 32= 13
Kếtiếp V5 = 0 (vì S 5 = 16 > 13)
V4 = 1, B - S6 - S5 = 45 - 32 - 8=5.
V3 = 1, B - S6 - S5 - S3 =45 - 32 - 8 - 4 = 1
V2 = 0, (vì S2 = 2 > 1).
V1 = 1, B - S6 - S4 - S3 -S1 = 45- 32 - 8 - 4 - 1 = 0
Dođó, ta được: V= (1, 0, 1, 1, 0, 1).
Phântích phương án trên chúng ta có thuật toán giải bài toán EKN như sau:
Input: S1,S2,..., Sn và B;
Output: V= (V1 , V2 ,..., Vn );
Actions:
for i:= n downto 1 do
begin
if B< Sithen Vi = 0
else
begin
Vi =1
B= B - Si
end;
end;
Sauđây là chương trình giải EKN với các khối lượng cho được bởi vectơ (1, 2, 4, 8,16, 32, 64, 128).
Program EASYKNAPSACK;
Usescrt;
Constn = 8;
Typemang = array[1..n] of integer;
Var V, S: mang;
B, i: integer;
Begin
clrscr;
write(' Nhap B= '); readln(B);
S[1]:= 1;
for i:= 2 to n do S[i]:= S[i -1]* 2;
for i:= 1 to n-1 do
begin
if B< S[n-i] then V[n-i]:= 0
else
begin
V[n-i] :=1;
B := B- S[n-i];
end;
end;
if B= 0 then
For i:= 1 to n do writeln(' V', i, '=',V[i])
else writeln(' Khong co giai phap! ');
readln;
End.
Linhhoạt từ bài toán Knapsack chúng ta sẽ có nhiều bài toán dạng này. Mời các bạnthử bài toán sau:
Bài toán: Chomột cái cân hai đĩa và n quả cân với khối lượng tương ứng d1 , d2 ,...,dn. Ta nói trọng lượng y có thể cân được từ các quả cân di ,i = 1..n, nếu xi di =y, với xi = {-1, 0, 1};
xi = -1, khi quả cân đặtcùng đĩa với vật cân;
xi = 0, khi quả cân khôngđược sử dụng;
xi = 1, khi quả cân dikhông đặt cùng đĩa với vật cân.
Bạnhãy lập chương trình in ra mọi khối lượng có thể cân được từ những quả cân đó?
