PUPASOFT BLOG!

เอาละครับหลังจากอ่านทฤษฎีกันไปเยอะแล้ว เรามาลองของจริงดูบ้างดีกว่า

จากคราวที่แล้ว
สมมติให้ input เป็นดังนี้
5 10
8 3000
3 1600
6 2500
1 600
4 1900

โดยเลข 5 ตัวแรกหมายถึงจำนวน card และ 10 หมายถึงจำนวนดาวสูงสุดที่จะหยิบได้
5 บรรทัดถัดมาจะประกอบด้วย จำนวนดาวและพลังโจมตี ตามลำดับ

วิธีการทำ จะใช้ตารางมาช่วยนะครับ ก่อนอื่นสร้างตารางที่เมื่อไม่มีการ์ดใบใดถูกเลือกเลย

เลขที่อยู่ในแต่ละช่องของตารางก็คือพลังโจมที่ดีที่สุดเมื่อเลือกแล้วนะครับ
เราจะมาเริ่มหยิบการ์ดกันนะครับ
เริ่มทีละ column โดยที่ column แรกจะเป็นการทดลองหยิบการ์ดใบแรก Blue Eyes White Dragon 8 ดาว พลังโจมตี 3000
จะเห็นได้ว่า ช่้อง 1 ดาว หยิบบลูอายส์ไม่ไ้ด้นะครับ เพราะดาวเกิน จะหยิบได้ก็เมื่อถึงช่องแปดดาวแล้ว
ลองทำ column แรกจะได้ตารางแบบนี้

จะเห็นได้ว่า เมื่อเลือกหยิบบลูอายส์ใบเดียวแล้ว
เราจะได้ 1 ดาว 2 ดาว 3 ดาว …. 7 ดาว ที่มีพลังโจมตีมากที่สุดเป็น 0 เพราะไม่สามารถใส่บลูอายส์ลงไปได้
แต่ที่ช่อง 8 9 10 จะเห็นได้ว่า เราได้เลือกบลูอายส์ ที่มีพลังโจมตี 3000

แล้วทำไมต้องมีเส้นสีน้ำเงิน??
เรามาลองดูกันตอนทำไปสักสองแถวดู จะได้ตารางแบบนี้

พอถึงตอนนี้จะเห็นได้ว่า ถ้าเรามีการ์ดแค่สองใบ แต่ต้องการหยิบให้ได้
ดาว        พลังโจมตีสูงสุด
0             0
1              0
2             0
3             1600
.
.
8             3000
9             3000
10          3000

แล้วเส้นสีน้ำเงินล่ะ??
สมมตินะครับ ถ้าเราต้องการหยิบ ให้ได้ 5 ดาว ที่ได้พลังโจมตีสูงที่สุด แต่การ์ดที่เราจะจับตอนนั้นมีแค่ 3 ดาว
เราก็เอาพลังโจมตีของการ์ดที่เราจะหยิบ + พลังโจมตีที่ดีที่สุดของ 2 ดาว เราก็จะได้ การ์ดรวมห้าดาวที่มีพลังโจมตีสูงสุดแล้วจริงใหมครับ

ในกรณีนี้คือ ช่อง 8 ดาว เราเลือกหยิบบลูอายส์ซึ่งมี 8 ดาว เพราะฉะนั้น เราจะต้องหา 0 ดาวที่มีพลังโจมตีสูงที่สุดมาเติม
(เป็นเหตุผลที่เราต้องตั้งค่าแถวแรกให้เป็นค่า 0 เนื่องจากหากเราเลือก 0 ดาวที่ดีที่สุด ค่าจะต้องเป็น 0)

เช่นเดียวกันกับช่อง 10 ดาว เราเลือกหยิบบลูอายส์ 8 ดาว เพราะฉะนั้น เราจะต้องหา 2 ดาวที่มีพลังโจมตีสูงที่สุดมาเติมแต่ 2 ดาวยังเป็น 0 อยู่เพราะเราเลือกหยิบบลูอายส์เป็นใบแรก
(เป็นเหตุผลที่เราต้องตั้งค่า column แรกให้เป็นค่า 0 ซึ่งเป็นค่าน้อยที่สุดที่เป็นไปได้)

ใน column 2 ก็เช่นเดียวกัน เพียงแต่ที่ช่อง 8 ดาวให้เรานำไปเปรียบเทียบกับค่าพลังโจมตีที่ดีที่สุดอันเก่าแล้วพบว่า ต่อให้เราเอา พลังโจมตีของ ซอมบี้ดราก้อน กับ 5 ดาวที่พลังโจมตีสูงที่สุด (1600+0) ก็ยังน้อยกว่าพลังโจมตี 8 ดาวเก่าที่ได้ที่สุด ดังนั้นเราจึงเลือกพลังโจมตีเก่านั่นเอง

เรามาลองทำจนจบดูนะครับ จะได้ตารางดังนี้

จะเห็นได้ว่า เราสามารถบอกได้หมดเลย ว่า 1 ดาวที่ดีที่สุดพลังโจมตีเท่าไหร่ 2 ดาวที่มีพลังโจมตีสูงที่สุด ….
จนถึงคำตอบของเรา 10 ดาวที่มีพลังโจมตีสูงที่สุด

บางคนอาจจะยังไม่เข้าใจ ให้ไล่ลองทำดูนะครับ ทีละขั้นตอน ผมจะสรุปขั้นตอนให้ดูง่ายๆ ละกัน
1. สร้างตาราง จำนวนของ(N) x จำนวนสูงสุดของข้อจำกัด(ดาว)
2. ที่ช่อง 0 ทั้งแนวนอนและแนวตั้ง ให้ตั้งค่าเป็นจำนวนที่น้อยที่สุดที่จะเป็นไปได้(ถ้าโจทย์ให้หาค่ามากที่สุดนะ)
3. ที่ช่องใดๆ ถ้าแถวดาว มากกว่า ดาวของการ์ดที่เราหยิบ แปลว่าเราจะสามารถหยิบการ์ดนี้ได้
4. นำพลังโจมตีของการ์ดที่เราหยิบ + ค่าที่(แถวบอกจำนวนดาว – ดาวของการ์ดที่เราหยิบ) ถ้าได้มากกว่า ค่าที่มากที่สุดของแถวเงื่อนไขนี้ ให้เปลี่ยนเป็นพลังโจมตีนั้นๆแทน
5. ถ้าไม่ ให้เลือกพลังโจมตีที่ดีที่สุดอันเดิม

แหม พอใช้ภาษาพูดแล้วงงๆ ใช่ใหมล่ะ งั้นลองเป็น code ดูนะครับ

Last 5 posts by p

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