418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 1

อินพุต: เซตของจำนวนเต็ม $A=\{a_{1},a_{2},...,a_{n}\}\,$ ที่มีสมาชิก $n\,$ ตัว และจำนวนเต็ม $S\,$

เอาพุต: คำตอบว่า "ใช่" หรือ "ไม่ใช่"

แนวคิด: เนื่องจากข้อนี้ต้องการตรวจสอบซับเซตทุก ๆ ซับเซตของ เซต $A\,$ ฉะนั้นวัตถุที่เราสนใจก็คือ ซับเซตนั่นเอง ซึ่งในห้องเรียนได้เรียนถึงวิธีการหยิบซับเซตขึ้นมาพิจารณาทีละซับเซตกันไปแล้ว เราก็จะใช้วิธีนั้นกัน นอกจากนี้โจทย์ข้อนี้ต้องการตรวจสอบว่าซับเซตที่เรากำลังพิจารณาอยู่นั้นมีค่าผลบวกเท่ากับจำนวนเต็ม $S\,$ หรือไม่ แสดงว่าเงื่อนไขก็คือ ผลบวกของซับเซตที่กำลังพิจารณาเท่ากับจำนวนเต็ม $S\,$ หรือไม่นั่นเอง

จากแนวคิดข้างต้นสามารถเขียนเป็น pseudocode ได้ดังนี้

SUM(A,G,n)

sum <- 0

for i<-0 to n-1

if g[i] = 1

sum = sum + A[i]

return(sum)

เนื่องจากจำนวนซับเซตที่พิจารณาทั้งหมดมี $2^{n}\,$ ซับเซต และแต่ละซับเซตต้องทำการตรวจสอบว่าผลบวกของมันเท่ากับ $S\,$ หรือไม่ ซึ่งใช้เวลาอย่างมาก $O(n)\,$ ดังนั้น เวลาการทำงานทั้งหมดของอัลกอริทึมคือ $O(n2^{n})\,$ นั่นเอง