Skip to main content

knapsack-problem

การทำความเข้าใจเกี่ยวกับ Knapsack Problem​

Knapsack Problem (ปัญหากระเป๋าของนักเดินทาง) เป็นปัญหาคลาสสิกในวิทยาการคอมพิวเตอร์และการวิจัยปฏิบัติการ ที่เกี่ยวข้องกับการเลือกไอเท็มจากชุดของไอเท็มที่มีน้ำหนักและค่าใช้จ่ายต่างกัน เพื่อให้สามารถบรรจุไอเท็มได้มากที่สุดในกระเป๋าที่มีน้ำหนักจำกัด

ปัญหานี้มีหลายรูปแบบ แต่ที่สำคัญและได้รับความนิยมมากที่สุดคือ 0/1 Knapsack Problem ซึ่งกำหนดให้คุณเลือกไอเท็มจากชุดของไอเท็มเพื่อเพิ่มค่าในกระเป๋าที่มีน้ำหนักจำกัด โดยแต่ละไอเท็มสามารถเลือกได้แค่หนึ่งครั้ง (ไม่สามารถเลือกไอเท็มได้ครึ่งหนึ่งหรือมากกว่าหนึ่งครั้ง)

1. ข้อกำหนดของปัญหา​

สมมติว่าเรามีชุดของไอเท็ม n ชิ้น โดยไอเท็มแต่ละชิ้นมีค่าใช้จ่าย (value) และน้ำหนัก (weight) ที่ระบุไว้:

  • ค่าใช้จ่าย ( v_i ) ของไอเท็ม ( i )
  • น้ำหนัก ( w_i ) ของไอเท็ม ( i )
  • กระเป๋ามีความจุจำกัดที่ W (ความจุสูงสุดของกระเป๋า)

คำถามคือ: ควรเลือกไอเท็มใดบ้างเพื่อให้ได้ค่าใช้จ่ายรวมสูงสุดโดยไม่เกินความจุของกระเป๋า ( W )?

2. รูปแบบของปัญหากระเป๋า (Knapsack Problem)​

0/1 Knapsack Problem​

ใน 0/1 Knapsack Problem เรามีไอเท็ม ( n ) ชิ้น และสามารถเลือกไอเท็มใด ๆ หรือไม่เลือกเลย โดยที่ไม่สามารถเลือกไอเท็มได้หลายครั้งหรือเลือกแค่บางส่วนของไอเท็ม

  • เลือกไอเท็ม ( i ) หรือไม่เลือก
  • เป้าหมายคือการเพิ่มค่าใช้จ่ายสูงสุดในขณะที่น้ำหนักไม่เกิน W

3. วิธีการแก้ไขปัญหากระเป๋าด้วย Dynamic Programming​

ในการใช้ Dynamic Programming (DP) เพื่อแก้ปัญหานี้ เราจะใช้ตาราง DP เพื่อเก็บค่าผลลัพธ์ของการเลือกไอเท็มที่ดีที่สุดในแต่ละกรณี

ขั้นตอนการทำงาน:​

  1. สร้างตาราง DP ที่มีขนาด ( (n+1) \times (W+1) ) โดยที่ ( n ) คือจำนวนไอเท็ม และ ( W ) คือความจุสูงสุดของกระเป๋า
  2. แถวที่ ( i ) ของตารางจะเก็บค่าของการเลือกไอเท็มจากชุดไอเท็มแรก ( i ) ชิ้น
  3. คอลัมน์ที่ ( w ) จะเก็บค่าของการเลือกไอเท็มโดยมีน้ำหนักสูงสุดไม่เกิน ( w )
  4. ค่าของตาราง DP จะถูกคำนวณดังนี้:
    • ถ้าไม่เลือกไอเท็ม ( i ): ค่าจะเท่ากับค่าที่ได้จากแถวก่อนหน้าในคอลัมน์เดียวกัน
    • ถ้าเลือกไอเท็ม ( i ): ค่าจะเท่ากับค่าของการเลือกไอเท็มที่มีน้ำหนักเหลือ ( w - w_i ) บวกกับค่าใช้จ่ายของไอเท็ม ( i )

สูตรการคำนวณ:​

  • หาก ( w_i \leq W ): [ DP[i][w] = \max(DP[i-1][w], DP[i-1][w - w_i] + v_i) ]
  • หาก ( w_i > W ): [ DP[i][w] = DP[i-1][w] ]

ตัวอย่างตาราง DP:​

ให้ชุดไอเท็มและกระเป๋าที่มีความจุสูงสุด ( W = 5 ):

  • สินค้า 1: ค่าใช้จ่าย 3, น้ำหนัก 2
  • สินค้า 2: ค่าใช้จ่าย 4, น้ำหนัก 3
  • สินค้า 3: ค่าใช้จ่าย 5, น้ำหนัก 4

ตาราง DP จะเริ่มต้นเป็น:

    W = 0   1   2   3   4   5
i
0  [ 0   0   0   0   0   0 ]
1  [ 0   0   3   3   3   3 ]
2  [ 0   0   3   4   4   7 ]
3  [ 0   0   3   4   5   7 ]

ในตารางนี้:

  • แถว 1 (สินค้า 1): สามารถเลือกไอเท็มที่มีน้ำหนัก 2 และค่าใช้จ่าย 3 ได้
  • แถว 2 (สินค้า 2): เลือกสินค้า 2 สามารถทำให้เราได้ค่าใช้จ่ายรวม 7 เมื่อเลือกสินค้า 1 และ 2
  • แถว 3 (สินค้า 3): หากเลือกสินค้า 3 ที่มีน้ำหนัก 4 และค่าใช้จ่าย 5 จะไม่สามารถเลือกสินค้าอื่นได้เนื่องจากกระเป๋ามีขนาดจำกัด

ค่าในตำแหน่ง ( DP[3][5] ) จะเป็นค่าใช้จ่ายรวมสูงสุดที่สามารถเลือกได้ ซึ่งคือ 7

4. Complexity ของ 0/1 Knapsack Problem​

  • Time Complexity: ( O(n \times W) ), โดยที่ ( n ) คือจำนวนไอเท็มและ ( W ) คือความจุของกระเป๋า
  • Space Complexity: ( O(n \times W) ) หากใช้ตาราง 2D เพื่อเก็บค่า DP หรือสามารถใช้การปรับปรุงตารางให้มีขนาด 1D เพื่อลดพื้นที่

5. Approximation Algorithms และ Fractional Knapsack​

ในกรณีที่เราใช้ Fractional Knapsack (กระเป๋าที่สามารถเลือกไอเท็มได้เป็นส่วนๆ) จะสามารถใช้ Greedy Algorithm แทนได้

Fractional Knapsack Problem:​

  • เราสามารถเลือกไอเท็มได้ครึ่งหนึ่งหรือมากกว่าหนึ่งชิ้น โดยเลือกไอเท็มที่มีอัตราส่วนของค่าใช้จ่ายต่อน้ำหนักสูงสุด

ขั้นตอน:

  1. คำนวณอัตราส่วน ( \frac{v_i}{w_i} ) สำหรับทุกไอเท็ม
  2. เลือกไอเท็มที่มีอัตราส่วนสูงสุดและเพิ่มเข้าไปในกระเป๋าจนกว่าจะเต็ม
  3. ถ้ากระเป๋ายังพอมีที่ว่างและสามารถใส่ส่วนหนึ่งของไอเท็มได้ ให้เลือกส่วนที่เหลือ

6. สรุป​

  • Knapsack Problem เป็นปัญหาการเลือกชุดของไอเท็มจากหลายๆ ชิ้น โดยไม่เกินน้ำหนักที่จำกัด เพื่อให้ค่าใช้จ่ายรวมสูงสุด
  • 0/1 Knapsack Problem ใช้ Dynamic Programming ในการหาคำตอบที่ดีที่สุด
  • Fractional Knapsack Problem สามารถใช้ Greedy Algorithm ในการหาคำตอบที่ดีที่สุด
  • ความซับซ้อนของ 0/1 Knapsack อยู่ที่ ( O(n \times W) ) ซึ่งเป็นปัญหาที่สามารถแก้ไขได้ด้วยวิธี Dynamic Programming