24.5 เก็บเส้นทางเพื่อพิมพ์คำตอบจริง

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

จดว่าชนะด้วยทางไหน

ตอนเติมช่อง x ของโจทย์ทอนเหรียญ เราลองทุกเหรียญแล้วเก็บค่าที่น้อยที่สุด ถ้าจดไว้ด้วยว่าเหรียญไหนทำให้ได้ค่านั้น ก็รู้ว่าเหรียญสุดท้ายของคำตอบที่ x บาทคือเหรียญอะไร หักเหรียญนั้นออกได้ x - c บาท ซึ่งก็จดไว้แล้วว่าเหรียญสุดท้ายคืออะไร เดินย้อนแบบนี้จนเหลือ 0 บาท

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

const int INF = 1000000000;

int main()
{
    int n, target;
    cin >> n >> target;
    vector<int> coins(n);
    for (int i = 0; i < n; i++) {
        cin >> coins[i];
    }
    vector<int> fewest(target + 1, INF);
    vector<int> last_coin(target + 1, 0); // (1)!
    fewest[0] = 0;
    for (int x = 1; x <= target; x++) {
        for (int c : coins) {
            if (c <= x && fewest[x - c] + 1 < fewest[x]) {
                fewest[x] = fewest[x - c] + 1;
                last_coin[x] = c; // (2)!
            }
        }
    }
    if (fewest[target] == INF) { // (3)!
        cout << "impossible\n";
        return 0;
    }
    cout << "coins = " << fewest[target] << '\n';
    int x = target;
    while (x > 0) { // (4)!
        cout << last_coin[x] << (x - last_coin[x] > 0 ? ' ' : '\n');
        x -= last_coin[x];
    }
    return 0;
}

1. อาเรย์ที่สองขนาดเท่าตาราง จดเหรียญสุดท้ายของคำตอบที่ดีที่สุดของแต่ละช่อง อาเรย์แบบนี้มักเรียกว่า parent หรือ choice
2. จดเฉพาะตอนที่ได้ค่าดีขึ้นจริง จึงเปลี่ยน min เป็น if ที่เทียบด้วย <
3. เช็กว่าทำได้ก่อนเดินย้อน ดูในส่วนลองทำให้พัง
4. เดินย้อนจากเป้าหมายลงไป แต่ละรอบหักเหรียญที่จดไว้ จบเมื่อเหลือ 0 บาท

3 13
1 3 4

coins = 4
1 4 4 4

เดินจาก 13 เหรียญสุดท้ายคือ 1 เหลือ 12 เหรียญสุดท้ายของ 12 คือ 4 เหลือ 8 แล้ว 4 แล้ว 0 เหรียญออกมาตามลำดับที่เดินย้อน ซึ่งกลับหัวกับลำดับที่ใส่ ถ้าโจทย์อยากได้ลำดับตอนใส่ ให้เก็บใส่ vector แล้ว reverse ตามหน้า 16.5 ก่อนพิมพ์

เมื่อมีหลายคำตอบที่ดีเท่ากัน

ทอน 4 บาทด้วยเหรียญ 1 2 3 ใช้ 2 เหรียญได้สองแบบ คือ 1 + 3 กับ 2 + 2 โปรแกรมเดิมพิมพ์แบบไหน ขึ้นกับลำดับเหรียญในข้อมูลเข้า เพราะเหรียญที่ลองก่อนและได้ค่าน้อยสุดจะถูกจดไว้ เหรียญหลังที่ได้ค่าเท่ากันไม่ทับ เพราะเทียบด้วย < ผลที่ได้จากการรันจริงคือ

ถูกทั้งคู่ ถ้าโจทย์ยอมรับคำตอบใดก็ได้ grader จะมีตัวตรวจพิเศษ แต่ถ้าโจทย์กำหนดว่าต้องพิมพ์แบบไหน เช่น "ถ้ามีหลายแบบ ให้ใช้เหรียญมูลค่ามากก่อน" ต้องเลือกให้ตรง ทั้งลำดับที่ลองและการเทียบด้วย < หรือ <= เป็นตัวกำหนด แบบฝึกหัดข้อ 8 ของบทนี้ให้ฝึกเรื่องนี้

เดินย้อนตารางโดยไม่จดเพิ่ม

บางครั้งไม่ต้องมีอาเรย์ที่สอง เพราะดูจากตารางก็รู้ว่าแต่ละช่องมาจากทางไหน บ้านติดกันในหน้า 24.4 มีแค่สองทาง ถ้า best[i] เท่ากับ best[i - 1] แปลว่าไม่ต้องเข้าหลังที่ i ก็ได้เท่านี้ ข้ามไปดูหลังที่ i - 1 ถ้าไม่เท่า แปลว่าค่านี้ได้มาจากการเข้าหลังที่ i เท่านั้น จดหลังที่ i แล้วกระโดดไปดูหลังที่ i - 2

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

int main()
{
    int n;
    cin >> n;
    vector<long long> money(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> money[i];
    }
    vector<long long> best(n + 1);
    best[0] = 0;
    best[1] = money[1];
    for (int i = 2; i <= n; i++) {
        best[i] = max(best[i - 1], best[i - 2] + money[i]);
    }
    vector<int> chosen;
    int i = n;
    while (i >= 1) {
        if (i >= 2 && best[i] == best[i - 1]) { // (1)!
            i -= 1;
        } else {
            chosen.push_back(i); // (2)!
            i -= 2;
        }
    }
    reverse(chosen.begin(), chosen.end()); // (3)!
    cout << "total = " << best[n] << '\n';
    cout << "houses =";
    for (int h : chosen) {
        cout << ' ' << h;
    }
    cout << '\n';
    return 0;
}

1. ไม่เข้าหลังที่ i ก็ได้ค่าเท่ากัน จึงไม่เข้า เช็ก i >= 2 ก่อน เพราะหลังที่ 1 ตาราง best[1] คือ a[1] ถ้าไปถึงหลังที่ 1 ได้แปลว่าต้องเข้า
2. ค่านี้ได้จากการเข้าหลังที่ i เท่านั้น จด แล้วข้ามหลังที่ i - 1 ซึ่งเข้าไม่ได้
3. เดินย้อนจึงได้เลขบ้านจากมากไปน้อย กลับลำดับให้เป็นน้อยไปมากก่อนพิมพ์

7
20 50 30 10 60 40 30

total = 140
houses = 2 5 7

50 + 60 + 30 = 140 ตรงกับตาราง ข้อนี้ก็มีคำตอบที่ดีเท่ากันอีกแบบ คือหลัง 1 3 5 7 ได้ 20 + 30 + 60 + 30 = 140 โปรแกรมเลือกแบบแรกเพราะตอนย้อนถึงหลังที่ 3 best[3] เท่ากับ best[2] คือ 50 จึงเลือกไม่เข้า ถ้าเปลี่ยนให้เลือกเข้าเมื่อค่าเท่ากัน ต้องเช็กว่า best[i - 2] + a[i] เท่ากับ best[i] แทน

ช่วงย่อยมากสุดเป็นวันไหน

Kadane ในหน้า 24.4 ตอบว่ากำไรมากสุดคือ 7 แต่เจ้าของร้านอยากรู้ว่าวันไหนถึงวันไหน ช่วงที่จบที่วัน i เริ่มที่ไหน ขึ้นกับว่าวัน i ต่อจากช่วงเดิมหรือเริ่มใหม่ จึงจดวันเริ่มไว้คู่กับทุกช่อง

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

int main()
{
    int n;
    cin >> n;
    vector<long long> profit(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> profit[i];
    }
    vector<long long> ending(n + 1);
    vector<int> start(n + 1); // (1)!
    ending[1] = profit[1];
    start[1] = 1;
    int best_end = 1;
    for (int i = 2; i <= n; i++) {
        if (ending[i - 1] + profit[i] >= profit[i]) { // (2)!
            ending[i] = ending[i - 1] + profit[i];
            start[i] = start[i - 1];
        } else {
            ending[i] = profit[i];
            start[i] = i;
        }
        if (ending[i] > ending[best_end]) { // (3)!
            best_end = i;
        }
    }
    cout << "best = " << ending[best_end] << '\n';
    cout << "days " << start[best_end] << " to " << best_end << '\n';
    return 0;
}

1. start[i] คือวันเริ่มของช่วงที่ดีที่สุดที่จบที่วัน i
2. ต่อจากช่วงเดิม วันเริ่มก็เป็นวันเริ่มเดิม ถ้าเริ่มใหม่ วันเริ่มคือวันนี้ ใช้ >= ให้ต่อช่วงเดิมเมื่อได้เท่ากัน จึงได้ช่วงที่ยาวกว่า
3. จำวันจบของช่วงที่ดีที่สุดแทนการจำค่า ใช้ > จึงได้ช่วงที่จบเร็วที่สุดเมื่อมีหลายช่วงเท่ากัน

8
-3 5 -2 4 -6 3 2 -1

best = 7
days 2 to 4

5 - 2 + 4 = 7 ตรงกัน ทั้งสามตัวอย่างในหน้านี้ใช้หลักเดียวกัน ตารางบอกว่าดีที่สุดได้เท่าไร ส่วนการตัดสินใจที่ทำให้ได้ค่านั้น ต้องจดไว้หรือคำนวณย้อนได้จากตาราง

ทำไมไม่เก็บคำตอบทั้งชุดไว้ในทุกช่อง

วิธีตรงไปตรงมาที่หลายคนคิดก่อน คือให้แต่ละช่องเก็บรายการเหรียญทั้งชุดเป็น vector<int> เวลาช่อง x ชนะด้วยเหรียญ c ก็คัดลอกรายการของช่อง x - c มาแล้วต่อท้ายด้วย c ถูกต้องเหมือนกัน แต่การคัดลอกแต่ละครั้งยาวเท่าคำตอบ ซึ่งยาวถึงราว X / 4 เหรียญเมื่อมีเหรียญ 4 บาท ทั้งเวลาและหน่วยความจำจึงเป็น O(X²) วัดบนเครื่องเดียวกับหน้า 24.1 ด้วยเหรียญ 1 3 4 รันแบบละ 5 ครั้ง ยกเว้นแถว 40000 ที่รัน 3 ครั้ง

เงินเพิ่มสองเท่า เวลาของการเก็บรายการเพิ่มราวสามถึงสี่เท่า ซึ่งเป็นลักษณะของ O(X²) ที่ 40000 บาท รายการทุกช่องรวมกันมีตัวเลขราว 2 × 10⁸ ตัว กินหน่วยความจำราว 800 MB เกินที่ grader ส่วนใหญ่ให้ไปมาก -O2 ก็ช่วยไม่ได้เพราะเวลาเกือบทั้งหมดคือการจองและคัดลอกหน่วยความจำ ส่วนการจดเหรียญสุดท้ายใช้อาเรย์เพิ่มแค่หนึ่งชุด เดินย้อนเพิ่มแค่เท่าจำนวนเหรียญในคำตอบ เติมสิบล้านช่องได้ในไม่ถึงครึ่งวินาที

ลองทำให้พัง

แบบที่ 1 เดินย้อนโดยไม่เช็กว่าทำได้

ในโปรแกรม coin-path ลบสี่บรรทัดที่เช็ก fewest[target] == INF ออก คิดว่าโจทย์ส่วนใหญ่ทำได้อยู่แล้ว แล้วป้อนแสตมป์ 5 กับ 7 บาท ราคา 23 บาทจากหน้า 24.3

2 23
5 7

coins = 1000000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

พิมพ์ INF เป็นจำนวนเหรียญ แล้วพิมพ์ 0 ไม่หยุดจนต้องปิดหน้าต่างเอง last_coin[23] ไม่เคยถูกจด จึงเป็น 0 ที่ใส่ไว้ตอนสร้าง หัก 0 บาทแล้วก็ยังเป็น 23 บาท ลูปไม่มีวันจบ ถ้าส่ง grader ข้อนี้จะได้ผลว่าเกินเวลา ทุกครั้งที่เดินย้อน ต้องแน่ใจว่าแต่ละรอบเดินเข้าใกล้จุดจบจริง เหมือนกฎของลูป binary search ในหน้า 19.1

แบบที่ 2 เดินย้อนด้วยเงื่อนไขผิด

ในโปรแกรม robber-path คิดว่า "ถ้าหลังที่ i มีเงินไม่มากกว่าหลังที่ i - 1 ก็ไม่ต้องเข้า" จึงเปลี่ยนเงื่อนไขของ if ในลูปเดินย้อนเป็น

if (i >= 2 && money[i] <= money[i - 1]) {

total = 140
houses = 2 5

ตัวเลข 140 ยังถูกเพราะมาจากตาราง แต่บ้านหลังที่ 2 กับ 5 ได้แค่ 50 + 60 = 110 ตอนอยู่ที่หลังที่ 7 เงิน 30 บาทน้อยกว่าหลังที่ 6 จึงข้ามไป แล้วเข้าหลังที่ 6 ไม่ได้เพราะ 40 น้อยกว่า 60 ทั้งที่คำตอบ 140 ต้องเข้าหลังที่ 7 การเดินย้อนต้องถามตารางว่า "ค่านี้มาจากทางไหน" เท่านั้น ห้ามใช้เหตุผลแบบ greedy มาแทน ตรวจได้ง่ายๆ ด้วยการบวกเงินของบ้านที่พิมพ์ออกมา แล้วเทียบกับ total ทุกครั้งที่ทดสอบ

สรุป

• ตาราง DP เก็บแค่ค่าที่ดีที่สุด ถ้าต้องการคำตอบจริงต้องรู้ว่าแต่ละช่องได้ค่ามาจากทางไหน
• วิธีแรก จดทางเลือกที่ชนะลงอาเรย์ที่สองขณะเติมตาราง แล้วเดินย้อนจากช่องคำตอบ
• วิธีที่สอง เดินย้อนตารางที่เติมเสร็จแล้ว ถามว่าค่าในช่องนี้ได้มาจากทางไหน
• เดินย้อนได้คำตอบกลับหัว ใช้ reverse ถ้าต้องการลำดับเดิม
• เมื่อมีหลายคำตอบที่ดีเท่ากัน ลำดับที่ลองและ < กับ <= เป็นตัวเลือกว่าได้แบบไหน
• เก็บคำตอบทั้งชุดไว้ทุกช่องเป็น O(X²) ทั้งเวลาและหน่วยความจำ จดเหรียญสุดท้ายเพิ่มแค่อาเรย์เดียว
• เช็กว่าทำได้ก่อนเดินย้อนเสมอ ไม่งั้นลูปไม่จบ

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด