January 7th, 2010
Dynamic Programming #2 ตอน Knapsack Problem
2 Comments », Programming, Programming Tips, by pสวัสดีครับ กลับมาพบกันอีกแล้วกับ tips ในการเขียนโปรแกรมยากๆ แต่มีประโยชน์มากมาย กับ Dynamic Programming
จากคราวที่แล้ว ได้เขียนเกี่ยวกับ Dynamic Programming แบบง่ายๆ ที่นี่
วันนี้เราจะมาลองกันแบบ Advance ขึ้นไปอีกขั้น นั่นก็คือ การเขียน Dynamic Programming เพื่อแก้ปัญหาประเภท Knapsack Problem
Knapsack Problem คืออะไร?
สมมติ มีการ์ดยูกิอยู่หลายใบ แต่ละใบจะมี level (ดาว) และพลังโจมตีต่างๆกัน หากให้เลือกการ์ดออกมาให้ครบ 10 ดาว และให้มีพลังโจมตีสูงที่สุด จะเลือกอย่างไร?
ตัวอย่างง่ายๆ
สมมติมีการ์ดอยู่ห้าใบ ดังนี้
Blue Eyes White Dragon 8 ดาว พลังโจมตี 3000
Dragon Zombie 3 ดาว พลังโจมตี 1600
Demon 6 ดาว พลังโจมตี 2500
Kuriboh 1 ดาว พลังโจมตี 600
Bloodwars 4 ดาว พลังโจมตี 1900
ให้เลือกอย่างมากได้สิบดาว ให้ได้พลังโจมตีสูงที่สุด จะทำอย่างไร
ยังจำตอนที่แล้วได้มั้ยครับ ที่ว่า ให้มองปัญหาใหญ่ให้กลายเป็นปัญหาย่อยๆ เล็กๆ แล้วก็ย่อยปัญหาเล็กลงไปอีกทีจนเลือกหน่วยที่เล็กที่สุด
จากโจทย์้ข้อนี้ก็เช่นเดียวกันครับ
- หากเราต้องการจะหยิบการ์ดใบสุดท้ายที่มี 4 ดาวแล้ว แสดงว่า การ์ดที่เราหยิบ 6 ดาวก่อนหน้าจะต้องได้พลังโจมตีมากที่สุด
- หากเราต้องการหยิบการ์ดรองสุดท้ายที่มี 1 ดาวแล้ว แสดงว่า การ์ดที่เราหยิบ 5 ดาวก่อนหน้าจะต้องได้พลังโจมตีมากที่สุด
- แต่หากเราต้องการหยิบการ์ดรองสุดท้ายที่มี 6 ดาวแล้ว แสดงว่า การ์ดที่เราหยิบ 0 ดาวก่อนหน้าจะต้องได้พลังโจมตีมากที่สุด – จบ
- แต่หากเราต้องการหยิบการ์ดรองสุดท้ายที่มี 3 ดาวแล้ว แสดงว่า การ์ดที่เราหยิบ 3 ดาวก่อนหน้าจะต้องได้พลังโจมตีมากที่สุด
….
เป็นเช่นนี้ไปเรื่อยๆ..
เป็นไงครับ ดูยากใช่ใหมครับ งั้นลองดูรูปนี้ดู
อาจจะดูง่ายขึ้นนิดหน่อย แต่ก็ยังงงใช่ใหมครับ ว่า มันต่างจากการ Recursion ตรงไหน
นั่นก็เพราะว่า Dynamic Programming จะให้ memory แทนการ run ที่สูญเปล่าไงครับ
อย่างเช่น หากมีการ์ด 4 ดาวในชุดอยู่สองใบ แล้วเราจะเลือกการ์ด 4 ดาวแต่ละใบ เราจำเป็นต้องแต่ recursive ไปทั้งสองทาง
ทั้งที่เป็นการหาการ์ดที่มีดาวรวม 6 ดาว และมีพลังโจมตีเยอะที่สุดเหมือนกันแท้ๆ
พูดถึงตรงนี้ พอมองภาพออกแล้วใช่ใหมครับ นี่ก็เป็นหลักการง่ายๆ (?) ของ Dynamic Programming นั่นเอง
ครั้งหน้าจะพูดถึงเรื่องของ การใช้ Dynamic Programming ในการเขียนโปรแกรมจริงๆ นะครับ
วันนี้ขอลาไปก่อน สวัสดีปีใหม่
Last 5 posts by p
- memset ในภาษาซี คืออะไรกันนะ? - January 13th, 2010
- Dynamic Programming #3 Knapsack Problem in Programming - January 7th, 2010
- การอ่าน/เขียนไฟล์ ที่มี character encoding ต่างๆ โดยภาษา Java - January 3rd, 2010
- วิธีการทำ Dynamic Programming - August 20th, 2009
- วิธีทำให้ netbeans รัน C/C++ ได้ - July 6th, 2009
เมพขิงๆ