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 = {u
i
; i =1..n} mỗi phần tử u
i
U có kích cỡ S(u
i
) và
số tự nhiênB.
Liệucó một tập con U' U sao cho S(u
i
)= B. Trong đó: u
i
U'.
Để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ử {u
1
,u
2
, u
3
, u
4
},
kích cỡ lần lượt là S(u
1
)= 1, S(u
2
) = 5, S(u
3
) = 2, S(u

+ U
2
' = {u
4
} (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à S
1
, S
2
,..., S
n
sao 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= (V
1
, V
2
,..., V
6
).Trong đó V
i
= 1 nếu vật thứ i

V
2
= 0, (vì S
2
= 2 > 1).
V
1
= 1, B - S
6
- S
4
- S
3
-S
1
= 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: S
1
,S
2
,..., S
n
và B;
Output: V= (V
1
, V
2
,..., V

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 d
1
, d
2
,...,d
n
. Ta
nói trọng lượng y có thể cân được từ các quả cân d
i
,i = 1..n, nếu x
i
d