24.1 จาก recursion สู่ตาราง

บทที่ 23 มีโจทย์ทอนเหรียญที่ greedy ตอบผิด มีเหรียญราคา 1 3 และ 4 บาท ต้องทอน 6 บาทให้ใช้เหรียญน้อยที่สุด greedy หยิบเหรียญใหญ่สุดก่อนได้ 4 + 1 + 1 สามเหรียญ แต่คำตอบจริงคือ 3 + 3 สองเหรียญ ทางที่ถูกแน่นอนคือลองทุกทาง แต่ลองทุกทางตรงๆ ช้ามาก หน้านี้ใช้โจทย์นี้ข้อเดียวพาไปครบสามแบบ คือ recursion ลองทุกทาง แล้วจดคำตอบแบบหน้า 9.3 แล้วเปลี่ยนเป็นลูปเติมตารางที่ไม่เรียกตัวเองเลย สามแบบนี้คือ dynamic programming (DP) ในสองหน้าตา

ลองทุกทางด้วย recursion

คิดจากเหรียญเหรียญแรกที่ยื่นให้ลูกค้า ถ้าต้องทอน x บาท เหรียญแรกเป็นได้แค่ 1 3 หรือ 4 บาท ยื่นเหรียญ c ไปแล้ว ที่เหลือคือทอน x - c บาทให้ใช้เหรียญน้อยที่สุด ซึ่งเป็นโจทย์แบบเดิมแต่เล็กลง ให้ fewest(x) คือจำนวนเหรียญน้อยที่สุดที่รวมได้ x บาท

fewest(0) = 0
fewest(x) = 1 + ค่าน้อยที่สุดของ fewest(x - c) ทุกเหรียญ c ที่ไม่เกิน x

แปลงเป็นโค้ดได้ตรงตัวแบบบทที่ 9 และนับจำนวนครั้งที่เรียกไว้ด้วยตัวแปร global แบบหน้า 9.3

#include <bits/stdc++.h>
using namespace std;

vector<int> coins = {1, 3, 4};
long long calls = 0;

int fewest(int amount)
{
    calls++;
    if (amount == 0) { // (1)!
        return 0;
    }
    int best = INT_MAX; // (2)!
    for (int c : coins) {
        if (c <= amount) {
            best = min(best, fewest(amount - c) + 1); // (3)!
        }
    }
    return best;
}

int main()
{
    int amount;
    cin >> amount;
    int answer = fewest(amount);
    cout << "fewest(" << amount << ") = " << answer << '\n';
    cout << "calls = " << calls << '\n';
    return 0;
}

1. กรณีฐาน ทอน 0 บาทไม่ต้องใช้เหรียญ
2. INT_MAX จากหน้า 20.2 เป็นค่าเริ่มต้นที่อะไรก็น้อยกว่า เหรียญ 1 บาทมีเสมอ จึงทอนได้ทุกจำนวนและ best ไม่ค้างที่ INT_MAX
3. ลองเหรียญ c เป็นเหรียญแรก ใช้ไปหนึ่งเหรียญ บวกกับจำนวนเหรียญน้อยที่สุดของเงินที่เหลือ

6

fewest(6) = 2
calls = 24

ได้ 2 ถูกต้อง แต่ใช้การเรียก 24 ครั้ง ภาพนี้คือทุกการเรียกตอนคำนวณ fewest(6) ตัวเลขในกล่องคือจำนวนเงินที่ยังต้องทอน กิ่งซ้ายคือยื่นเหรียญ 1 กิ่งกลางคือเหรียญ 3 กิ่งขวาคือเหรียญ 4

กล่อง 3 ทางขวาบนทำงานเดียวกับกล่อง 3 ทางซ้ายทุกอย่าง ทั้งกิ่งย่อยใต้มันด้วย กล่อง 2 โผล่สี่ครั้ง กล่อง 1 โผล่หกครั้ง จำนวนเงินที่ต่างกันมีแค่ 0 ถึง 6 รวม 7 ค่า ที่เหลือคือ คำนวณปัญหาย่อยเดิมซ้ำ แบบเดียวกับต้นไม้ฟีโบนัชชีในหน้า 9.3

ช้าแค่ไหน

ป้อนจำนวนเงินมากขึ้นแล้วดูจำนวนครั้งที่เรียก จากนั้นตัดบรรทัดนับออกแล้วจับเวลาด้วย clock() แบบหน้า 9.3 วัดบนโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 Windows 11 กับ GCC 14.2 ของ Code::Blocks ทั้งแบบ Code::Blocks (-Wall อย่างเดียว) และแบบ -O2 ทุกช่องคือค่ากลางของการรัน 5 ครั้ง ยกเว้น 45 บาทแบบ Code::Blocks ที่รันครั้งเดียวเพราะรอนานเกินไป

เงินเพิ่มทีละ 5 บาท จำนวนครั้งเพิ่มราว 11 เท่าทุกแถว ทอนแค่ 45 บาทก็รอกว่าหนึ่งนาทีแบบ Code::Blocks ทั้งที่จำนวนเงินที่ต่างกันมีแค่ 46 ค่า เวลาแบบนี้เรียกว่าโตแบบทวีคูณ (exponential) ตามที่บทที่ 18 เตือนไว้

จดคำตอบ แบบ top-down

แก้ด้วยวิธีของหน้า 9.3 ทุกประการ คำนวณ fewest(x) ได้ครั้งแรกเมื่อไรก็จดลง memo[x] ครั้งต่อไปตอบจากสมุดเลย ต่างจากหน้า 9.3 แค่ใช้ vector ที่สร้างตามขนาดของข้อมูลเข้า แทนอาเรย์ขนาดตายตัว

#include <bits/stdc++.h>
using namespace std;

vector<int> coins = {1, 3, 4};
vector<int> memo; // (1)!
long long calls = 0;

int fewest(int amount)
{
    calls++;
    if (amount == 0) {
        return 0;
    }
    if (memo[amount] != -1) { // (2)!
        return memo[amount];
    }
    int best = INT_MAX;
    for (int c : coins) {
        if (c <= amount) {
            best = min(best, fewest(amount - c) + 1);
        }
    }
    memo[amount] = best; // (3)!
    return best;
}

int main()
{
    int amount;
    cin >> amount;
    memo = vector<int>(amount + 1, -1); // (4)!
    int answer = fewest(amount);
    cout << "fewest(" << amount << ") = " << answer << '\n';
    cout << "calls = " << calls << '\n';
    return 0;
}

1. สมุดจดเป็น global เพราะทุกชั้นของ recursion ต้องเห็นเล่มเดียวกัน ยังไม่รู้ขนาดจนกว่าจะอ่านจำนวนเงิน จึงประกาศว่างไว้ก่อน
2. -1 แปลว่ายังไม่เคยคำนวณ จำนวนเหรียญไม่มีทางติดลบ จึงไม่สับสนกับคำตอบจริง
3. จดก่อนคืนค่า ถ้าลืมบรรทัดนี้ โปรแกรมจะช้าเท่าเดิมทั้งที่คำตอบถูก ตามที่เห็นในหน้า 9.3
4. สร้าง vector ใหม่ amount + 1 ช่อง ทุกช่องเป็น -1 แล้วใส่ทับ memo ที่ว่างอยู่ ตามที่หน้า 16.1 บอกว่า vector คัดลอกได้ทั้งก้อน

6

fewest(6) = 2
calls = 14

14 ครั้งตรงกับภาพข้างบนพอดี คือกล่องสีหลัก 9 กล่องกับกรอบส้ม 5 กล่อง ส่วนกล่องเส้นประ 10 กล่องไม่ถูกเรียกเลย ป้อน 40 ได้ calls = 116 จากเดิมสามร้อยกว่าล้านครั้ง ป้อน 1000 ได้ calls = 2996 จำนวนเงินแต่ละค่าคำนวณจริงครั้งเดียว ครั้งนั้นเรียกต่อไม่เกินสามครั้ง จำนวนครั้งที่เรียกจึงไม่เกินราวสามเท่าของจำนวนเงิน

แบบนี้เรียกว่า top-down (บนลงล่าง) เพราะเริ่มถามจากปัญหาใหญ่ที่ต้องการ แล้วให้ recursion ไล่ลงไปหาปัญหาย่อยเอง ข้อดีคือเขียนต่อจาก recursion เดิมได้เลย เพิ่มแค่สี่จุด

เติมตาราง แบบ bottom-up

ดูต้นไม้อีกครั้ง กว่า fewest(6) จะได้คำตอบ ต้องรู้ fewest(5) fewest(3) และ fewest(2) ก่อน และทุกค่าก็ต้องรู้ค่าที่น้อยกว่าตัวเองก่อนเสมอ ถ้าอย่างนั้นก็ไม่ต้องให้ recursion ไล่ลงไปหา คำนวณจากน้อยไปมากเองเลย เริ่มจาก 0 บาท แล้ว 1 บาท 2 บาท ไปเรื่อยๆ พอถึงช่องไหน ช่องที่น้อยกว่าที่ต้องใช้ก็เติมไว้ครบแล้ว

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> coins = {1, 3, 4};
    int amount;
    cin >> amount;
    vector<int> dp(amount + 1);
    dp[0] = 0; // (1)!
    for (int x = 1; x <= amount; x++) { // (2)!
        dp[x] = INT_MAX;
        for (int c : coins) {
            if (c <= x) {
                dp[x] = min(dp[x], dp[x - c] + 1); // (3)!
            }
        }
    }
    for (int x = 0; x <= amount; x++) {
        cout << "dp[" << x << "] = " << dp[x] << '\n';
    }
    return 0;
}

1. ช่องแรกของตารางคือกรณีฐานเดิม เขียนให้เห็นชัดแม้ vector จะเริ่มที่ 0 อยู่แล้ว
2. เติมจากช่องน้อยไปช่องมาก ลำดับนี้สำคัญที่สุดของแบบตาราง ดูในส่วนลองทำให้พัง
3. สูตรเดียวกับ recursion ทุกตัวอักษร แค่เปลี่ยน fewest(x - c) เป็นการอ่านช่อง dp[x - c] ที่เติมไว้แล้ว

6

dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 1
dp[4] = 1
dp[5] = 2
dp[6] = 2

ภาพนี้คือจังหวะที่เติมช่อง 6 ช่อง 5 3 และ 2 ที่มีกรอบสีเติมค่าไว้แล้ว ยื่นเหรียญ 1 เหลือ 5 บาทใช้ 2 เหรียญ ยื่นเหรียญ 3 เหลือ 3 บาทใช้ 1 เหรียญ ยื่นเหรียญ 4 เหลือ 2 บาทใช้ 2 เหรียญ ทางเหรียญ 3 ดีที่สุด dp[6] จึงเป็น 1 + 1 = 2

แบบนี้เรียกว่า bottom-up (ล่างขึ้นบน) หรือ tabulation (การเติมตาราง) ไม่มี recursion เลย จึงไม่มี call stack ให้เต็ม และไม่ต้องเสียเวลาเรียกฟังก์ชัน ต้องแลกด้วยการคิดเองว่าจะเติมช่องไหนก่อน

เทียบสามแบบ

ทั้งสามแบบใช้สูตรเดียวกัน ต่างกันแค่วิธีพาไปถึงปัญหาย่อย

X คือจำนวนเงิน K คือจำนวนชนิดเหรียญ ตารางมี X + 1 ช่อง แต่ละช่องลองเหรียญ K ชนิด งานทั้งหมดจึงราว X × K หน้า 24.2 จะใช้หลักนี้กับทุกโจทย์ วัดบนเครื่องเดียวกับข้างบน รันแบบละ 5 ครั้ง

0.000 คือเร็วเกินกว่าที่ clock() วัดได้ ตารางนี้ไม่มี top-down ตอนเงินเป็นล้าน เพราะมันพังก่อน ดูในส่วนลองทำให้พัง เลือกแบบไหนดี ถ้าลำดับการเติมคิดง่ายและข้อมูลใหญ่ ใช้ bottom-up ถ้าลำดับคิดยาก หรือปัญหาย่อยที่ถูกถามจริงมีน้อยกว่าตารางทั้งตารางมาก ใช้ top-down ส่วนใหญ่ของบทนี้กับบทที่ 25 จะใช้ bottom-up

ลองทำให้พัง

แบบที่ 1 top-down กับจำนวนเงินมาก

ใช้โปรแกรม coin-memo เดิมทุกตัวอักษร คอมไพล์แบบ Code::Blocks แล้วรันใน PowerShell บนเครื่องที่เขียนเอกสารนี้ ป้อน 18000 ได้ fewest(18000) = 4500 ทั้ง 5 ครั้งที่ลอง แต่ป้อน 19000 โปรแกรมปิดตัวโดยไม่พิมพ์อะไรทั้ง 5 ครั้ง

Process returned -1073741571 (0xC00000FD)

0xC00000FD คือ stack overflow แบบหน้า 9.1 fewest(19000) เรียก fewest(18999) ซึ่งเรียก fewest(18998) ต่อลงไปเรื่อยๆ ก่อนจะมีชั้นไหนจบ stack จึงต้องซ้อนหนึ่งหมื่นเก้าพันชั้น จดคำตอบช่วยลดจำนวนครั้งที่เรียก แต่ไม่ได้ช่วยเรื่องความลึก แบบ -O2 ลึกได้มากกว่าเล็กน้อย ผ่านที่ 25000 พังที่ 26000 แต่ก็ยังห่างจากหลักล้านมาก ส่วน bottom-up ไม่มีความลึกเลย เติมสิบล้านช่องได้ในครึ่งวินาที โจทย์ที่ขอบเขตเป็นแสนเป็นล้าน จึงควรเขียนแบบตาราง

แบบที่ 2 เติมตารางผิดลำดับ

ในโปรแกรม coin-table เปลี่ยนลูปนอกให้เติมจากช่องมากไปช่องน้อย คิดว่ายังไงก็เติมครบทุกช่องเหมือนกัน

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> coins = {1, 3, 4};
    int amount;
    cin >> amount;
    vector<int> dp(amount + 1);
    dp[0] = 0;
    for (int x = amount; x >= 1; x--) {
        dp[x] = INT_MAX;
        for (int c : coins) {
            if (c <= x) {
                dp[x] = min(dp[x], dp[x - c] + 1);
            }
        }
    }
    for (int x = 0; x <= amount; x++) {
        cout << "dp[" << x << "] = " << dp[x] << '\n';
    }
    return 0;
}

6

dp[0] = 0
dp[1] = 1
dp[2] = 1
dp[3] = 1
dp[4] = 1
dp[5] = 1
dp[6] = 1

ทุกช่องได้ 1 ราวกับว่าเหรียญเดียวทอนได้ทุกจำนวน ตอนเติมช่อง 6 ช่อง 5 ยังไม่ได้เติม ค่าในนั้นจึงเป็น 0 ที่ vector ใส่ไว้ตอนสร้าง โปรแกรมเข้าใจว่าทอน 5 บาทไม่ต้องใช้เหรียญเลย ไม่มี error ไม่มี warning กฎของแบบตารางคือ ช่องที่สูตรอ่าน ต้องเติมเสร็จก่อนช่องที่กำลังเติมเสมอ สูตรนี้อ่านช่องที่น้อยกว่า จึงต้องเติมจากน้อยไปมาก

สรุป

• recursion ที่ลองทุกทางคำนวณปัญหาย่อยเดิมซ้ำ เวลาโตแบบทวีคูณ ทอนแค่ 45 บาทก็เรียกสามพันกว่าล้านครั้ง
• top-down คือ recursion เดิมที่จดคำตอบลงสมุดก่อนคืนค่า และเปิดสมุดก่อนคำนวณ
• bottom-up คือเติมตารางด้วยลูป จากปัญหาย่อยที่เล็กที่สุดขึ้นไป ใช้สูตรเดียวกันแต่อ่านจากช่องในตาราง
• ทั้งสองแบบคำนวณแต่ละปัญหาย่อยครั้งเดียว ทอนเงิน X บาทด้วยเหรียญ K ชนิดเป็น O(XK)
• top-down ลึกเท่าจำนวนเงิน พังด้วย stack overflow ที่หลักหมื่น bottom-up ไม่มีปัญหานี้
• เติมตารางต้องเติมช่องที่สูตรอ่านให้เสร็จก่อน เติมผิดลำดับได้คำตอบผิดเงียบๆ