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 ได้ดังนี้ <geshi lang="c"> SUM(A,G,n) {

   sum <-- 0
   for i=0 to n-1
   {
        if G[i] = 1
        {
              sum = sum + A[i]
        }
   }    
   return(sum)

} </geshi>

<geshi lang="c"> GENERATE(k) {

    if k=0
    {     
        v<--SUM(A,G,n)
        if (v=S)
        {
             return 1
        }else{ 
             return 0
        }
     }else{
        for G[k-1]= 1 to G[k-1]=2
        {
             GENERATE(k-1)
        }
     }

} </geshi>

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