Bài toán cái túi trong Pascal

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 đó: ui 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ử {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à