204512-53/lecture10

Dynamic Programming

ปัญหาที่ 1 เกมเก็บคะแนน

จากรูปแต่ละ node มีคะแนนอยู่ ต้องเริ่มจาก start ไปยัง end ให้ได้คะแนนรวมสูงสุดจะทำอย่างไร
วิธีการที่ง่ายที่สุดคือคำนวณผลรวมจากทุกเส้นทางแล้วหาเส้นทางที่มากที่สุด จากความสูง k จะใช้เวลา O(2^k)

พิจารณาปัญหาแบบ bottom-up ดูจากโหนดที่ 1 -> 2 -> … -> n ที่โหนด 2 และ โหนด 3 การจะไปที่โหนด 5 จะเกิดการทับซ้อนของปัญหา จะต้องการเลือกเส้นทางที่มีคะแนนมากกว่า

พิจารณาปัญหาแบบ top-down ดูจากโหนดที่ n -> (n-1) -> … -> 1 สังเกตโหนดที่ 5 จะเกิดการทับซ้อนของปัญหา จะต้องการเลือกเส้นทางที่มีคะแนนมากกว่าจาก 2 เส้นทางคือโหนด 2 หรือโหนด 3

ปัญหาที่ 2 วิธีการเดินทาง

วิธีเดินทางจากโหนด A ไปยังโหนด B ไปได้กี่วิธี

วิธีที่ง่ายสุดนับทุกเส้นทางจากโหนด A ไปยังโหนด B จากรูปมีเส้นเชื่อมโหนดครบทุกเส้นทำให้สามารถคำนวณได้เลยไม่ต้องนับ จะได้ ${\binom {8}{5}}$ หรือ ${\binom {8}{3}}$ จะได้ 56 วิธี

จากรูปด้านบนถ้าเส้นเชื่อมไม่ครบทุกโหนดการคำนวณทำได้ยาก การจะนับทีละเส้นทางจาก A -> B ใช้เวลานาน ถ้าพิจารณาจากโหนด B ย้อนกลับขึ้นไป การจะรู้ค่าที่โหนด B ต้องรู้ค่าของ 2 โหนดก่อนหน้า โหนดก่อนหน้าก็ต้องรู้ค่าของโหนดก่อนหน้าถัดไปอีกเรื่อยๆ จนถึงโหนด A ดังนั้นถ้ามีการบันทึกค่าที่โหนดปัจจุบันไว้จะทำให้โหนดถัดมาค่าได้เลยไม่ต้องเริ่มใหม่ทำให้หาวิธีเดินทางได้ 20 วิธีดังนี้

ปัญหาที่ 3 ปัญหาการขึ้นบันได

มีบันได n ขั้น มีวิธีการเดินขึ้น 2 วิธี คือ เดินขึ้นทีละขั้น หรือเดินขึ้นทีละ 2 ขั้น จะมีรูปแบบในการขึ้นไปถึงขั้นที่ n กี่รูปแบบ

พิจารณาจากขั้นที่ n จำนวนรูปแบบการขึ้นบันไดมาขั้นที่ n ต้องรู้รูปแบบการขึ้น 2 ขั้นก่อนหน้า (ขั้นที่ n-1 และ n-2) ถ้าให้ F(n) แทนจำนวนรูปแบบการขึ้นบันไดขั้นที่ n จะได้ว่า F(n) = F(n-1)+F(n-2)

ปัญหาที่ 4 การแบ่งหุ้น

มีใบหุ้น nใบ แต่ละใบมีมูลค่า a₁, a₂, a₃, …, a_n จะจัดได้กี่รูปแบบ
ถ้ามีใบหุ้น 10 ใบมูลค่าดังนี้ 1, 4, 2, 1, 3, 4, 7, 10, 16 จัดรูปแบบได้ดังนี้

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47
0	x
1	x	x
4	x	x			x	x
2	x	x	x	x	x	x	x
1	x	x	x	x	x	x	x	x
3	x	x	x	x	x	x	x	x	x	x	x
4	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
7	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
10	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
16	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x