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

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

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

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

ให้อะเรย์ A เก็บค่าจำนวนเต็ม $n/,$ ตัว อะเรย์ G แต่ละช่องเก็บค่า 1 หรือ 2 ถ้า G[i] เก็บค่า 1 หมายถึง สมาชิกตัวที่ i ในอะเรย์ A เป็นสมาชิกของซับเซต แต่ถ้าเก็บค่า 2 คือไม่เป็นสมาชิกของซับเซต

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

SUM(A,G,n)

sum <-- 0

for i=0 to n-1

if G[i] = 1

sum = sum + A[i]

if(sum=S)

return(1)

else

return(0)

GENERATE(k)

if k=0

v<--SUM(A,G,n)

if (v)

return 1

else

return 0

else

for G[k-1]= 1 to G[k-1]=2

GENERATE(k-1)

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