Thứ Hai, ngày 07 tháng 5 năm 2012

// // Leave a Comment

Bài toán ba lô - The kanpsack Algorithm

Bài toán: Cho 1 cái ba lô được nhét đầy các đồ vật cho ở hình dưới (trọng lượng tính theo grams). Biết rằng ba lô nặng 3064 grams, bạn có thể xác định những vật có trong ba lô đó không ?



Vấn đề trở nên phức tạp và khó tính toán khi trong ba lô chứa 100 đồ vật. Tuy nhiên, nếu cách sắp xếp khối lượng đồ vật có vài thông tin đặc biệt "trapdoor" đã được biết trước, và người có được thông tin đó sẽ dễ dạng tìm được thông tin bí mật. Tức là, 100-bit thông tin đó xác định được những đồ vật có trong ba lô.

0 comments: