การเขียนโปรแกรมแบบไดนามิก Dynamic programming
การเขียนโปรแกรมไม่ใช่เพียงการเรียงคำสั่งเพื่อบอกให้คอมพิวเตอร์ทำงานใดงานหนึ่งเท่านั้น แต่หลายครั้ง เป็นการแก้ปัญหาซับซ้อนที่ต้องการความคิดสร้างสรรค์ ลองนึกถึงโจทย์ปัญหาที่มีหลายชั้นสับปลับทับซ้อนกัน ทำอย่างไรเราจึงจะทะลวงไปยังคำตอบที่ถูกต้องได้อย่างมีประสิทธิภาพ? นี่คือจุดที่ "การเขียนโปรแกรมแบบไดนามิก" (Dynamic Programming, หรือ DP) สามารถเข้ามาแสดงบทบาทได้อย่างเด่นชัด
การเขียนโปรแกรมแบบไดนามิก เป็นวิธีการหนึ่งในการออกแบบอัลกอริทึมที่เหมาะกับปัญหาที่มีความซ้ำซ้อน (overlapping subproblems) และการนำคำตอบของปัญหาย่อยมาใช้ซ้ำ (optimal substructure) เราแยกปัญหาที่ซับซ้อนออกเป็นปัญหาย่อยๆ ที่ต่อเมื่อรวมคำตอบของปัญหาย่อยเหล่านั้นแล้วจะได้คำตอบของปัญหาใหญ่
ลองเริ่มต้นด้วยโจทย์ง่ายๆ เช่น การหาจำนวนวิธีที่จะเดินทางจากจุด A ไปถึงจุด B ในแผนที่ที่มีหลายทางเลือก เราอาจจะหามาตรฐานในการตัดสินใจทีละขั้นตอน คำตอบของแต่ละขั้นจะช่วยให้เรารู้วิธีเดินทางไปต่อได้ ทีนี้เราจะไม่จำเป็นต้องพิจารณาวิธีเดินทางทั้งหมดทุกครั้งที่เริ่มเดินทางใหม่ แค่ใช้คำตอบที่ได้จากการเดินทางก่อนหน้านี้มาประยุกต์ใช้ นี่คือหลักการพื้นฐานของการเขียนโปรแกรมแบบไดนามิก
ตัวอย่างปัญหาที่สามารถแก้ไขด้วยวิธีนี้เช่น ปัญหาการหาคำตอบสำหรับ "การตัดแท่งเหล็ก" ที่เราต้องการทราบวิธีการตัดที่จะทำให้ได้ราคาที่ดีที่สุด เราสามารถหาคำตอบสำหรับการตัดเหล็กที่ยาวกว่าโดยพิจารณาจากการตัดเหล็กที่มีความยาวน้อยกว่า ซึ่งได้คำนวณไว้ล่วงหน้าแล้ว
ในโปรแกรมมิ่ง การจัดเก็บข้อมูลคำตอบของปัญหาย่อยที่เรียกว่า "Memoization" จะช่วยให้เราไม่ต้องคำนวณคำตอบสำหรับปัญหาย่อยเดียวกันซ้ำๆ เราจะเก็บคำตอบเหล่านั้นในโครงสร้างข้อมูล เช่น อาร์เรย์หรือแฮชแมพ เพื่อนำกลับมาใช้ได้ทันที เมื่อเราจะต้องคำนวณคำตอบสำหรับปัญหาที่ใหญ่ขึ้น
ลองพิจารณาตัวอย่างโค้ดภาษา Python ซึ่งแสดงถึงการใช้งานการเขียนโปรแกรมแบบไดนามิกโดยเฉพาะ:
def fib(n, memo={}):
if n in memo:
return memo[n]
if n <= 2:
return 1
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
print(fib(50))
ในตัวอย่างนี้, `fib` เป็นฟังก์ชันที่คำนวณหาค่า Fibonacci แต่แทนที่จะใช้วิธีเดิมๆ ที่มีประสิทธิภาพต่ำ เราใช้ memoization เพื่อจดจำคำตอบที่ได้คำนวณไว้แล้ว ทำให้ฟังก์ชันสามารถคำนวณได้เร็วขึ้นอย่างมาก
Knapsack problem
เป็นปัญหาที่ก าหนดให้มีวัตถุหลายๆ ชิ้น ต้องการเอาของใส่ถุงเป้โดยให้
ผลรวมของราคาของวัตถุมีค่ามากที่สุด
วัตถุแต่ละชิ้นมีน้าหนักและมีราคาอยู่
ผลรวมของ น้ำหนักที่ถุงเป้จะรับได้ไม่เกินค่าบางค่า W
ดังนั้นเราจะต้องพิจารณาน้ำหนักพร้อมกับมูลค่าของสินค้าพร้อมๆกัน
สำหรับปัญหานี้จะมี 2 version
1. 0-1 knapsack problem
2. Fractional knapsack problem (แบ่งของเป็นชิ้นย่อยๆ ได้)
แบบที่ 1 สิ่งของแบ่งย่อยไม่ได้: ดังนั้นเราสามรถเลือกหยิบหรือไม่หยิบ
แก้ด้วย Dynamic programming
แบบที่ 2 สิ่งของแบ่งย่อยได้: เราสามารถเลือกส่วนของสิ่งของมาได้ แก้
ด้วย Greedy algorithm
การใช้ Dynamic Programming ในการแก้ปัญหา Knapsack เป็นวิธีที่มีประสิทธิภาพสำหรับปัญหาที่มีลักษณะการเลือกหรือไม่เลือกสิ่งของเข้าไปในกระเป๋าที่มีข้อจำกัดเรื่องน้ำหนัก โดยมีเป้าหมายเพื่อให้ได้มูลค่าสูงสุด วิธีการนี้จะเก็บผลลัพธ์ของปัญหาย่อยไว้และใช้มันเพื่อสร้างคำตอบสำหรับปัญหาที่ใหญ่ขึ้น
def knapSack(W, weight, value, n):
K = [[0 for w in range(W + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, W + 1):
if weight[i-1] <= w:
K[i][w] = max(K[i-1][w], K[i-1][w-weight[i-1]] + value[i-1])
else:
K[i][w] = K[i-1][w]
return K[n][W]
- `W` คือน้ำหนักสูงสุดที่กระเป๋าสามารถรับได้
- `weight` คือลิสต์ที่บันทึกน้ำหนักของแต่ละสิ่งของ
- `value` คือลิสต์ที่บันทึกมูลค่าของแต่ละสิ่งของ
- `n` คือจำนวนสิ่งของ
- `K` คือตารางที่ใช้สำหรับเก็บค่าผลลัพธ์ของปัญหาย่อย
- ฟังก์ชัน `knapSack` คืนค่ามูลค่าสูงสุดที่สามารถบรรทุกในกระเป๋าได้โดยไม่เกินน้ำหนักที่กำหนด
จากที่เราได้เรียนรู้และพิจารณาถึงประโยชน์ของการเขียนโปรแกรมแบบไดนามิก ผู้อ่านคงเห็นได้ว่าพื้นฐานและตัวอย่างที่เรานำเสนอไม่ใช่เพียงแค่ทฤษฎี แต่ยังประยุกต์ใช้กับปัญหาในโลกจริงได้อีกด้วย สำหรับผู้ที่มีความสนใจในการเรียนรู้และฝึกฝนการเขียนโปรแกรมแบบนี้โดยลึกซึ้งยิ่งขึ้น ที่ EPT หรือ Expert-Programming-Tutor คือสถานที่ที่คุณสามารถเจาะลึกได้ถึงแก่นสารของการเขียนโปรแกรม เพื่อให้คุณได้พัฒนาทักษะ และก้าวสู่การเป็นนักพัฒนาที่มีพรสวรรค์และความรู้ที่แข็งแกร่ง
ที่ EPT เราเชื่อมั่นว่าการเรียนรู้การเขียนโปรแกรมไม่ใช่แค่เรียนภาษาและโค้ดง่ายๆ แต่เป็นการสร้างมูลฐานที่มั่นคงให้กับนักเรียนทุกคน ทั้งการเข้าใจหลักการความคิด และการประยุกต์ใช้เข้ากับสถานการณ์จริง เพื่อยกระดับความสามารถในการแก้ปัญหา และนำพาไปสู่การเป็นผู้เชี่ยวชาญที่แท้จริง์
หากคุณมองหาโอกาสในการเรียนรู้และเติบโต สมัครเรียนกับเราที่ EPT ได้เลยวันนี้ และร่วมเดินทางไปกับการสร้างสรรค์ผลงานโปรแกรมมิ่งที่ไม่สิ้นสุด!
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากเจอข้อผิดพลาด หรือต้องการพูดคุย ติดต่อได้ที่ https://m.me/expert.Programming.Tutor/
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM