Bài toán cái túi trong Pascal
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (74.28 KB, 4 trang )
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
4
) = 3 và B = 3.Bạn dễ dàng thấy rằng
có hai phương án:
+ U
1
' = {u
1
, u
3
}vì S(u
1
)+ S(u
3
) = 3
+ U
2
' = {u
4
}vì S (u
4
) = 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ó:
+ U
1
' = {u
1
, u
3
} (1, 0, 1, 0)
+ 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
được bỏ vào ba lô, V
i
= 0ngược lại vật bị để ngoài.
Chúngta thấy:
V
6
= 1, B - S
6
= 45 - 32= 13
Kếtiếp V
5
= 0 (vì S
5
= 16 > 13)
V
4
= 1, B - S
6
- S
5
= 45 - 32 - 8=5.
V
3
= 1, B - S
6
- S
5
- S
3
=45 - 32 - 8 - 4 = 1
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
n
);
Actions:
for i:= n downto 1 do
begin
if B< S
i
then V
i
= 0
else
begin
V
i
=1
B= B - S
i
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 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
i
=y, với x
i
= {-1, 0,
1};
x
i
= -1, khi quả cân đặtcùng đĩa với vật cân;
x
i
= 0, khi quả cân khôngđược sử dụng;
x
i
= 1, khi quả cân d
i
khô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 đó?
