PUPASOFT BLOG!

สวัสดีครับ มาพบกับผมอีกแล้ว วันนี้จะมานำเสนอวิธีการเขียน dynamic programming กันนะครับ

Dynamic Programming คืออะไร?
- Dynamic Programming คือการเขียนโปรแกรมแบบคุ้มค่าที่สุด คือจะไม่มีการทำซ้ำในส่วนที่ทำไปแล้ว โดย code ที่สามารถเขียนได้ด้วย Dynamic Programming นั้น จะสามารถเขียนด้วย Recursion แบบธรรมดาได้เช่นกัน แต่ความเร็วต่างกับเป็นพันเท่า

หลักการง่ายๆ
- ถ้าเราต้องการค่าที่มากที่สุดที่มีตัวที่ n รวมอยู่ด้วย นั่นก็คือ ค่าที่มากที่สุดของ n-1 รวมกับ n
ตัวอย่าง
จงหาเส้นทางที่มีผลรวมมากที่สุดจากบนลงมาข้างล่าง โดยสามารถ เดินลงได้แค่สองทางจากตัวมันเท่านั้น (แกล้งเป็นมองไม่เห็น “_” ไปก่อนนะครับ)
__ 1
_ 2 5
_3 7 6
9 2 4 8

จะเห็นได้ว่า การเขียนแบบ recursion ธรรมดาก็สามารถทำได้ โดยการเดินไปทุกเส้นทางที่เป็นไปได้ แล้วนำหาค่าที่มากที่สุด
แต่ถ้าใช้หลักการหมิก(ผมขอเรียก dynamic programming สั้นๆว่า หมิก นะครับ ขี้เกียจพิมพ์) เราจะหาค่ามากที่สุดไปเรื่อยๆขณะที่เดิน เรามาลองดูกันเลยดีกว่า

อันดับแรก
แถวแรก ไม่มีตัวที่อยู่เหนือกว่า ให้คงไว้
แถวที่สอง มีตัวที่เหนือกว่าอยู่ตัวเดียวคือ 1 ให้เอามาบวก จะได้
__ 1
_ 3 6
_3 7 6
9 2 4 8

แุถวที่สาม เลข 3 และ 6 มีตัวที่อยู่เหนือกว่าเพียงตัวเดียว ให้นำมาบวกกันโดยตรง จะได้
_     1
_   3 6
_6 7 12
9  2 4  8

ส่วนเลข 7 นั้น จะมีตัวที่เหนือกว่าอยู่สองตัวด้วยกัน ดังนั้น ให้นำมาเปรียบเทียบกันว่า ตัวไหนมากกว่า จึงนำตัวนั้นมาบวก จะได้
_     1
_   3 6
_6 13 12
9 2   4   8

ทำเช่นเดียวกัน ในชั้นถัดไป จะได้ตารางสุดท้ายเป็นรูปแบบ
_     1
_   3 6
_6 13 12
15 15 17 20

เท่านี้ เพียงแค่หาตัวที่มากที่สุดของแถวสุดท้าย ซึ่งก็คือ 20 เราก็จะได้ค่าผมรวมที่มากที่สุด โดยที่ใช้การวนแค่ n รอบเท่านั้น ในขณะที่การใช้ recursion ต้องใช้ถึง 4×3x2×1 รอบทีเดียว

ลองกลับไปฝึกทำกับโจทย์อื่นๆดูนะครับ เป็นวิธีที่มีประโยชน์มากๆเลย ลองกับโจทย์นี้ดู

จงหาค่าผลรวมที่มากที่สุดโดยหยิบจากชุดตัวเลขต่อไปนี้ โดย ห้ามหยิบตัวที่อยู่ติดกันเป็นอันขาด
9 2 3 7 1 5 6 6 9

ครั้งหน้าเราจะมาลองทำ dynamic แบบ advance ดูนะครับ

Last 5 posts by p

• memset ในภาษาซี คืออะไรกันนะ? - January 13th, 2010
• Dynamic Programming #3 Knapsack Problem in Programming - January 7th, 2010
• Dynamic Programming #2 ตอน Knapsack Problem - January 7th, 2010
• การอ่าน/เขียนไฟล์ ที่มี character encoding ต่างๆ โดยภาษา Java - January 3rd, 2010
• วิธีทำให้ netbeans รัน C/C++ ได้ - July 6th, 2009