(ทางผู้เขียนขอแนะนำให้ท่านอ่าน กำหนดการพลวัตเบื้องต้น ก่อนที่จะเริ่มอ่านหน้านี้นะคะ เพราะเนื้อหาจะต่อเนื่องกัน)

เอาล่ะ เราจะเริ่มมาพูดถึงปัญหาที่ยากขึ้นแล้วนะคะ จะขออนุญาตอธิบายละเอียดน้อยลง เพื่อให้ผู้อ่านได้ลองคิดตามมากขึ้น แต่ถ้ามีอะไรสงสัยหรืออยากพูดคุยก็คอมเมนท์ไว้ได้เช่นเคยค่ะ ^^

โจทย์: Coins

เราคงรู้กันแล้ว ว่าประเทศไทย มีเหรียญ 1,2,5 และ 10 บาท (ขอไม่พิจารณาเหรียญ 25 สตางค์ และ 50 สตางค์)

สมมติว่าเรามีเหรียญทุกชนิด ชนิดละไม่จำกัดจำนวน สมมติว่าเราจะจ่ายเงิน 27 บาท โดยใช้จำนวนเหรียญน้อยที่สุด
พิจาณาเหรียญที่ใหญ่ที่สุดก่อน.. เหรียญสิบ เราก็หยิบเหรียญสิบ สองเหรียญ (20 บาท)
ต่อมา เหรียญห้า… หยิบเหรียญห้ามาหนึ่งเหรียญ (25 บาท)
แล้วก็หยิบเหรียญสองบาท อีกหนึ่งเหรียญ เป็นเงิน 27 บาทพอดี

วิธีคิดแบบนี้ เป็นการคิดแบบละโมบ (Greedy) ก็คือ การเลือกทางเลือกที่ดีที่สุดสำหรับปัจจุบัน ซึ่งจะขออนุญาตไม่พูดถึง ณ ที่นี้

สำหรับเหรียญที่มีในประเทศไทย การคิดแบบละโมบนี้จะให้คำตอบที่ถูกต้อง แต่ทว่า…

สมมติว่าในประเทศไทย ไม่ได้มีแต่เหรียญ 1 บาท 2 บาท 5 บาท และ 10 บาท แต่มีเหรียญ 7 บาทด้วย
เมื่อคุณต้องการจะทอนเงิน 14 บาท การคิดแบบ Greedy จะเลือกเหรียญ 10,2,2 ให้คุณ เป็นจำนวนสามเหรียญ
แต่ถ้าคุณใช้เหรียญ 7 บาทเพียงสองเหรียญ ก็สามารถทอนเงิน 14 บาทได้แล้ว

ทำอย่างไรดี?

ลองสังเกตว่า สมมติเราต้องการรวมเงินให้ได้ n บาท แล้วเรามีเหรียญ 1, 2, 5, 7, 10 ให้เลือก

ถ้าสมมติเรารู้ว่า คำตอบที่ดีที่สุดมีเหรียญสิบ ก็สามารถหาคำตอบที่ดีที่สุดของ n-10 บาท แล้วเพิ่มเหรียญสิบไปอีกหนึ่งเหรียญในคำตอบนั้นได้

แต่เราไม่รู้นี่นา… ว่าเรามีเหรียญสิบในคำตอบที่ดีที่สุด

แต่คำตอบที่ดีที่สุดต้องมีซักเหรียญใน 1, 2, 5, 7, 10 บาทแน่นอน เราก็ลองทำทุกกรณี จะได้ว่า

การทอนเงิน n บาทโดยใช้เหรียญน้อยที่สุด ใช้เหรียญ = จำนวนเหรียญที่ใช้ในกรณีดีที่สุดของ n-1, n-2, n-5, n-7, n-10 บาท + 1 เหรียญ นั่นคือ

$dp_n = min( dp_{n-1}, dp_{n-2}, dp_{n-5}, dp_{n-7}, dp_{n-10}) + 1$

เช่น

$dp_{14} = min( dp_{13}, dp_{12}, dp_9, dp_7, dp_4) + 1$ ซึ่งใน $dp_{13}, dp_{12}, dp_9, dp_7, dp_4$ นั้น $dp_7$ มีค่าน้อยที่สุด คือ 1 เหรียญ

(หมายความว่า วิธีที่ดีที่สุดที่ทอนเงิน 14 บาท จะใช้จำนวนเหรียญเท่ากับ วิธีที่ดีที่สุดที่จะทอนเงิน 13, 12, 9, 7 หรือ 4 บาท บวกอีกหนึ่งเหรียญ)

ที่เหลือลองไปคิดดูนะคะ ^^ อย่างเช่น จะกำหนดเงื่อนไขเริ่มต้นอย่างไร

ลองทำเอง

ลองเอาข้อนี้ไปเขียนโปรแกรมดูนะคะ เวอร์ชั่นที่ input เหรียญเองได้ ว่ามีเหรียญอะไรบ้าง และตอบมาว่า ทอนเงิน k บาท ต้องใช้เหรียญอะไรบ้าง อย่างละกี่เหรียญ (ทำใน $O(k$ × จำนวนชนิดเหรียญ $)$ )
Nugget Number สำหรับข้อนี้มีวิธีที่ไม่ต้องใช้ dynamic แต่ถ้าเราใช้หมิก เราจะสามารถแก้ปัญหาได้ใน O(n) ค่ะ

Longest Increasing Subsequence

กำหนดตัวเลขมา $n$ ตัว $a_1,a_2,\cdots,a_n$
ให้เลือกมาบางตัวในนี้ ให้ได้จำนวนมากที่สุด
สมมติเราเลือก $a_i$ กับ $a_j$ มา
ถ้า $i<j$ แล้ว $a_i$ ต้องน้อยกว่า $a_j$ ด้วย (พูดง่ายๆ คือ ตัวซ้ายต้องน้อยกว่าตัวขวา)
จะเรียกลำดับนี้ว่า Longest Increasing Subsequence (ขอย่อว่า LIS)

เช่น

1 7 6 3 5 2

ตัวอักษรสีแดงคือตัวอักษรที่อยู่ใน LIS

วิธีทำ

นี่จะเป็นหมิกข้อแรกที่เราจะพิจารณาตัวก่อนหน้านี้ทุกตัว ไม่ใช่แค่บางตัว ทำให้การรันเป็น $O(n^2)$ (มีวิธีที่จะทำได้ใน $O(n log n)$ แต่จะยังไม่พูดถึงนะคะ)

ให้ $dp_k$ แทน ความยาวของ LIS ที่มากที่สุด ที่จบด้วย $a_k$

ในการหา $dp_k$ เราจะพิจารณาว่า $a_k$ จะเอามาต่อท้ายตัวไหนได้บ้าง

คำตอบก็คือ ทุกตัวที่อยู่ทางซ้ายของ $a_k$ และมีค่าน้อยกว่า $a_k$
ดังนั้น $dp_k = max(dp_i) + 1$ สำหรับทุก $i$ ที่น้อยกว่า $k$ และ $a_i$ < $a_k$

ในกรณีที่ยกตัวอย่างให้ดู ( 1 7 6 3 5 2 )

$dp_1 = 1$ คือความยาวของลำดับ 1
$dp_2 = 2$ คือความยาวของลำดับ 1,7
$dp_3 = 2$ คือความยาวของลำดับ 1,6
$dp_4 = 2$ คือความยาวของลำดับ 1,3
$dp_5 = 3$ คือความยาวของลำดับ 1,3,5
$dp_6 = 2$ คือความยาวของลำดับ 1,2

คำตอบก็คือ $max(dp_i)$ สำหรับ $i = 1..n$ เพราะเราไม่แน่ใจว่าตัวไหนมากสุด (หรือจะเก็บ max ระหว่างทำไว้เลยก็ได้)

ลองทำเอง

เขียนโปรแกรมหา LIS โดยให้ตอบด้วยว่ามีตัวไหนอยู่ใน LIS บ้าง
Weighted Interval Scheduling

สมมติว่าเรามีห้องหนึ่งห้อง ที่จะเอาไว้ให้คนอื่นมาเช่า มีหลายคนที่จะมาเช่าในช่วงเวลาต่างๆกัน เช่น คนหนึ่งอาจจะอยากเช่าตั้งแต่เวลา 3 ถึงเวลา 12 (เป็นช่วงปิด)
ห้องมีห้องเดียวเท่านั้น เราก็เลยให้คนสองคนเช่าพร้อมกันไม่ได้ (เช่นคนนึงอยากเช่าในเวลา 9-14 อีกคนอยากเช่า 14-17 จะให้เช่าได้แค่คนเดียวในสองคนนี้)
ถ้าสมมติว่าเราอยากให้จำนวนคนได้เช่ามากที่สุด มีวิธี greedy ที่จะใช้แก้ปัญหานี้ได้
แต่ในกรณีนี้ แต่ละคนจะให้เงินไม่เท่ากันด้วย
เราอยากเปิดห้องให้เช่า โดย ให้เราได้เงินมากที่สุด

ตัวอย่าง
มีคนเช่า 4 คน คือ

1-6 ให้ราคา 10 บาท
2-4 ให้ราคา 5 บาท
5-6 ให้ราคา 3 บาท
7-9 ให้ราคา 4 บาท

ในกรณีนี้ ก็จะให้คนแรกเช่าระหว่าง 1-6 และให้คนสุดท้ายเช่าในช่วง 7-9 ได้เงินรวม 14 บาท
ลองทำให้ได้ใน $O(n^2)$ เมื่อ n คือจำนวนคนที่มาเช่า
คำใบ้(โปรดแรเงาเพื่อดู): { ลองประยุกต์จากวิธี greedy ดู และอาจต้องใช้การ sort มาช่วย }

โจทย์อื่นๆ

สามเหลี่ยมตัวเลข (โจทย์คัดเลือกตัวแทนศูนย์สอวน. ปีพ.ศ.2549)

มีตัวเลขอยู่หลายตัว จำนวน $n \le 60$ แถว เรียงเป็นสามเหลี่ยม เช่นในภาพ

ให้เขียนโปรแกรมหาทางเดินจากบรรทัดบนสุด ลงมาบรรทัดล่างสุด โดยให้ได้มูลค่ารวมมากที่สุด (คำตอบแสดงด้วยตัวอักษรสีแดง)
โดยจะเดินลงมาได้อย่างเดียว และไปได้แค่ตัว ซ้ายล่าง และ ขวาล่าง ของมัน เท่านั้น
ถ้าทำเป็น recursive ธรรมดาจะเป็น $O(2^n)$ นะคะ ลองทำใน $O(n^2)$ ดู

ไดนามิกบนกราฟ

ต่อไปเราจะมาเริ่มหมิกแบบใหม่นะคะ ก็คือ หมิกบนกราฟนั่นเอง

โจทย์: เส้นทางที่ยาวที่สุด

สมมติว่าเรามี weighted DAG (Directed Acyclic Graph) อยู่กราฟหนึ่ง (กราฟมีทิศทาง ที่ไม่มี cycle และบนแต่ละเส้นเชื่อม มีน้ำหนัก)
เราต้องการเดินจากจุดเริ่มต้นหนึ่ง (เรียก node S) ไปยังจุดจบหนึ่ง (เรียก node T) โดยให้ได้ระยะทางยาวที่สุด

เราจะหมิกยังไงล่ะ? ก่อนหน้านี้หมิกได้ เพราะว่าเรารู้ลำดับไม่ใช่เหรอ ว่าตัวไหนต้องทำก่อนตัวไหน

เทคนิค: Memoization

“หมิก”ที่พูดถึงมาทั้งหมดนั้น จะสังเกตได้ว่า เกิดจากปัญหาเล็ก ที่เราขยายไปปัญหาใหญ่ขึ้น ในตอนนี้ เราจะลองมองปัญหาใหญ่ก่อน แล้วค่อยๆแก้ปัญหาเล็ก แต่จะไม่แก้ปัญหาเล็กนั้นซ้ำ

ยังจำข้อ Fibonacci ได้อยู่ไหมคะ

ขออนุญาตยกข้อนั้นมาพูดถึงอีกทีนะคะ

ในตอนนั้น เราได้สมการว่า $F_n = F_{n-1} + F_{n-2}$ แล้วเราหา $F_{n-1}$ และ $F_{n-2}$ ก่อน $F_n$

สำหรับ memoization เราจะเริ่มจากการสั่งหา $F_n$ โดยฟังก์ชั่นจะหา $F_{n-1}$ และ $F_{n-2}$ ให้เองโดยใช้การ recursive ดังตัวอย่างนี้

int F[1000];
 
int Fibonacci(int a)
{
    if(F[a]==-1) //ยังไม่เคยหาค่าตัวนี้
        F[a] = Fibonacci(a-1) + Fibonacci(a-2);
    return F[a];
}
 
int main()
{
    for(i=0;i<1000;i++) //กำหนดค่าเริ่มต้น ให้ F[i] เป็น -1 ทั้งหมด (เป็นการบอกว่า ยังไม่เคยหาค่านี้)
        F[i]=-1;
    F[0] = 0; //กำหนดเงื่อนไขเริ่มต้น
    F[1] = 1; //กำหนดเงื่อนไขเริ่มต้น
    Fibonacci(100);
}

สังเกตได้ว่าโค้ดดังกล่าวจะไม่หาค่า $F$ เดิมซ้ำ

สำหรับข้อ Fibonacci การเขียนแบบนี้นั้น เขียนยากกว่าแบบ dynamic ธรรมดาอีก แต่ในบางกรณีก็มีประโยชน์ค่ะ

ย้อนกลับมาข้อเดิม

ในข้อนี้แหละ ที่จะได้เห็นประโยชน์ของ memoization!

กำหนดให้ $dp_k$ แทน ระยะทางของเส้นทางที่ยาวที่สุดจาก S ถึง $k$ เมื่อ $k$ เป็น node ใดๆ

สังเกตว่า (ถ้า $k$ ไม่ใช่ node เริ่มต้น) เส้นทางที่ยาวที่สุดจาก S ถึง $k$ จะต้องผ่าน node สัก node หนึ่ง ที่มี edge ชี้มาที่ $k$ เสมอ (ขอเรียก node นี้ว่า $u$ )

ดังนั้นเราจะได้ว่า
$dp_k = max( dp_u + weight(u,k) )$ สำหรับทุก $u$ ที่ มี edge ไป $k$

ดังนั้นสามารถเรียก recursive หา $dp_u$ ทุกตัวมาเปรียบเทียบกันได้

หมายเหตุ

สำหรับข้อนี้ ก็สามารถใช้ dynamic ธรรมดาได้ ไม่จำเป็นต้องใช้ memoization แต่อย่างใด โดยการทำการ topological sorting แล้ว dynamic ธรรมดาตามลำดับ

(จริงๆ dynamic กับ memoization ก็ใช้แทนกันได้เกือบทุกกรณี แต่ในบางครั้ง memoization อาจสะดวกในการเขียนมากกว่า บางครั้ง dynamic ประหยัดหน่วยความจำมากกว่า ฯลฯ )

ลองทำเอง

ทุกข้อในหน้านี้ และ ในกำหนดการพลวัตเบื้องต้น แบบใช้ memoization
กำหนดตารางขนาด m×n และกำหนดบางช่องที่เดินผ่านไม่ได้ ถามว่า เดินจากช่องบนซ้ายสุดไปช่องล่างขวาสุด โดยเดินไปทางขวาและลงอย่างเดียว (ห้ามขึ้นและไปทางซ้าย) ได้กี่วิธี ให้ทำใน O(mn)
มี DAG ให้หนึ่งกราฟ กำหนด S และ T ถามว่า เส้นทางจาก S ไป T มีทั้งหมดกี่เส้นทาง
มี DAG ให้หนึ่งกราฟ กำหนด S และ T บนแต่ละ node มีของมูลค่า k (ติดลบได้) โดยถ้าเดินผ่านต้องเก็บของด้วย ให้เดินจาก S ไป T ให้เก็บของให้ได้มูลค่ามากที่สุด ต้องเดินอย่างไร

ถ้าอ่านไม่เข้าใจลองอ่านซ้ำดูนะคะ แล้วถ้ามีข้อติชม ข้อสงสัย ก็คอมเมนท์ไว้ได้เลยค่ะ ผู้เขียนอาจจะเขียนไม่รู้เรื่องเอง - -“

Navigation

กำหนดการพลวัต 2 (Dynamic Programming 2)

โจทย์: Coins

ลองทำเอง

Longest Increasing Subsequence

วิธีทำ

ลองทำเอง

โจทย์อื่นๆ

ไดนามิกบนกราฟ

โจทย์: เส้นทางที่ยาวที่สุด

เทคนิค: Memoization

ย้อนกลับมาข้อเดิม

หมายเหตุ

ลองทำเอง

Comments