23.3 เรียงงาน เส้นตาย และ knapsack แบบแบ่งได้

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

จัดคิวให้เวลารอรวมน้อยที่สุด

ครูตรวจงานนักเรียนทีละคน คนที่ i ใช้เวลาตรวจ t_i นาที ทุกคนมายืนรอพร้อมกันตั้งแต่นาทีที่ 0 คนหนึ่งต้องรอจนกว่าทุกคนที่อยู่ก่อนหน้าตรวจเสร็จ ครูจะเรียกคนไหนก่อนก็ได้ อยากให้ ผลรวมของเวลารอของทุกคน น้อยที่สุด ถ้ามีสี่คนใช้เวลา 7 3 1 5 นาที แล้วเรียกตามลำดับที่มา คนแรกรอ 0 คนที่สองรอ 7 คนที่สามรอ 7 + 3 = 10 คนที่สี่รอ 11 รวม 28 นาที

เวลาตรวจของคนแรกในคิวถูกนับซ้ำในเวลารอของทุกคนที่อยู่หลังเขา คนที่อยู่หน้าคิวจึงควรเป็นคนที่ใช้เวลาน้อย กฎ greedy คือ เรียกคนที่ใช้เวลาน้อยที่สุดก่อน (shortest job first)

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

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> jobs(n);
    for (int i = 0; i < n; i++) {
        cin >> jobs[i].first;
        jobs[i].second = i + 1; // (1)!
    }
    sort(jobs.begin(), jobs.end());
    long long clock_now = 0, total_wait = 0;
    for (int i = 0; i < n; i++) {
        cout << "student " << jobs[i].second << " waits " << clock_now << '\n';
        total_wait += clock_now; // (2)!
        clock_now += jobs[i].first;
    }
    cout << "total wait = " << total_wait << '\n';
    return 0;
}

1. เก็บหมายเลขนักเรียนคู่กับเวลา เพราะเรียงแล้วลำดับเปลี่ยน แต่ยังอยากพิมพ์ว่าใครได้ก่อน
2. คนนี้รอจนถึงเวลาปัจจุบัน แล้วเวลาปัจจุบันจึงเดินต่อไปอีกเท่ากับเวลาตรวจของเขา ผลรวมโตได้ถึงราว N² คูณเวลาตรวจ ใช้ long long

4
7 3 1 5

student 3 waits 0
student 2 waits 1
student 4 waits 4
student 1 waits 9
total wait = 14

ลดจาก 28 เหลือ 14 นาที เหตุผลว่าทำไมน้อยที่สุดใช้การแลกคนที่อยู่ติดกัน สมมติในคิวไหนก็ตามมีคน A ที่ใช้เวลา a อยู่ก่อนคน B ที่ใช้เวลา b ติดกัน และ a มากกว่า b ถ้าสลับให้ B ขึ้นก่อน

• B รอน้อยลง a นาที เพราะไม่ต้องรอ A แล้ว
• A รอนานขึ้น b นาที เพราะต้องรอ B
• คนอื่นรอเท่าเดิม คนที่อยู่ก่อนสองคนนี้ไม่เกี่ยว คนที่อยู่หลังก็รอทั้ง a และ b เหมือนเดิม

ผลรวมเปลี่ยนไป b - a ซึ่งติดลบ แปลว่าคิวไหนที่มีคนใช้เวลามากอยู่ติดหน้าคนใช้เวลาน้อย ยังทำให้ดีขึ้นได้ คิวที่ดีที่สุดจึงต้องไม่มีคู่แบบนั้นเลย ซึ่งก็คือคิวที่เรียงจากน้อยไปมาก ตรงกับ greedy

เทียบกับการลองทุกลำดับด้วย next_permutation ในหน้า 16.5 ซึ่งมี N! ลำดับ

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

int main()
{
    int n;
    cin >> n;
    vector<int> minutes(n);
    for (int i = 0; i < n; i++) {
        cin >> minutes[i];
    }
    vector<int> order(n);
    for (int i = 0; i < n; i++) {
        order[i] = i;
    }
    long long best = LLONG_MAX;
    long long tried = 0;
    do {
        long long clock_now = 0, total_wait = 0;
        for (int i = 0; i < n; i++) {
            total_wait += clock_now;
            clock_now += minutes[order[i]];
        }
        best = min(best, total_wait);
        tried++;
    } while (next_permutation(order.begin(), order.end()));
    cout << "orders tried = " << tried << '\n';
    cout << "best total wait = " << best << '\n';
    return 0;
}

4
7 3 1 5

orders tried = 24
best total wait = 14

ลองครบ 24 ลำดับ ได้ 14 เท่ากับ greedy วัดบนเครื่องเดียวกับหน้า 23.1 เวลาตรวจสุ่ม 1 ถึง 60 นาที รันแต่ละแบบ 5 รอบ

เพิ่มคนทีละคน การลองทุกลำดับช้าลงราวสิบเท่า เพราะ N! โตเร็วกว่า 2^N อีก ส่วนการเรียงรับคนเป็นล้านได้ในเสี้ยววินาที

งานที่มีเส้นตาย

น้องมีการบ้าน N ชิ้น ชิ้นที่ i ใช้เวลาทำ t_i วันเต็ม และต้องส่งภายในสิ้นวันที่ d_i ทำได้ทีละชิ้น เริ่มวันที่ 1 ถ้าชิ้นไหนเสร็จหลังเส้นตาย จะสายเท่ากับวันที่เสร็จลบ d_i ชิ้นที่เสร็จทันถือว่าสาย 0 วัน อยากจัดลำดับให้ ชิ้นที่สายที่สุดสายน้อยที่สุด คำตอบ 0 แปลว่าส่งทันทุกชิ้น

กฎ greedy คือ ทำชิ้นที่เส้นตายเร็วที่สุดก่อน (earliest deadline first) โดยไม่สนเลยว่าแต่ละชิ้นใช้เวลานานแค่ไหน

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

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> tasks(n);
    for (int i = 0; i < n; i++) {
        int days, due;
        cin >> days >> due;
        tasks[i] = {due, days};
    }
    sort(tasks.begin(), tasks.end());
    int today = 0, worst = 0;
    for (int i = 0; i < n; i++) {
        int due = tasks[i].first;
        int days = tasks[i].second;
        today += days;
        int late = max(0, today - due);
        cout << "due " << due << " done " << today << " late " << late << '\n';
        worst = max(worst, late);
    }
    cout << "max late = " << worst << '\n';
    return 0;
}

4
3 4
2 2
1 7
4 9

due 2 done 2 late 0
due 4 done 5 late 1
due 7 done 6 late 0
due 9 done 10 late 1
max late = 1

ข้อมูลเข้าแต่ละบรรทัดคือจำนวนวันที่ใช้กับเส้นตาย ถ้าใช้กฎจากหัวข้อที่แล้ว ทำชิ้นที่ใช้เวลาน้อยก่อน ลำดับจะเป็นชิ้น 1 วัน 2 วัน 3 วัน 4 วัน เสร็จวันที่ 1 3 6 10 ชิ้น 3 วันที่ต้องส่งวันที่ 4 เสร็จวันที่ 6 สาย 2 วัน แย่กว่า greedy ที่สายไม่เกิน 1 วัน กฎที่ถูกกับโจทย์หนึ่งจึงอาจผิดกับโจทย์ที่ดูคล้ายกัน

เหตุผลใช้การแลกคู่ที่ติดกันอีกครั้ง สมมติชิ้น X อยู่ติดหน้าชิ้น Y แต่เส้นตายของ X ช้ากว่าของ Y ให้ T เป็นวันที่ Y เสร็จ ซึ่งก็คือวันที่ทั้งคู่ทำเสร็จ

• ก่อนสลับ Y เสร็จวันที่ T สาย T - d_Y
• หลังสลับ Y เสร็จเร็วขึ้น สายไม่มากกว่าเดิม ส่วน X เสร็จวันที่ T สาย T - d_X ซึ่งน้อยกว่า T - d_Y เพราะ d_X มากกว่า
• ชิ้นอื่นเสร็จวันเดิมทั้งหมด

ค่าสายมากสุดหลังสลับจึงไม่เพิ่มขึ้น สลับไปเรื่อยๆ จนเรียงตามเส้นตาย ก็ยังดีไม่น้อยกว่าเดิม ลำดับตามเส้นตายจึงดีที่สุด ทั้งหมดเป็น O(N log N) จากการเรียง ถ้าโจทย์ถามแค่ว่าส่งทันทุกชิ้นได้ไหม ก็ใช้โปรแกรมเดียวกันแล้วดูว่าคำตอบเป็น 0 หรือไม่

knapsack แบบแบ่งได้

รถเข็นผลไม้รับน้ำหนักได้ W กิโลกรัม สวนมีผลไม้ N ชนิด ชนิดที่ i มีอยู่ w_i กิโลกรัม ขายได้ทั้งหมด v_i บาท ผลไม้ชั่งขายจึงตักไปแค่บางส่วนได้ ได้เงินตามสัดส่วน อยากขนไปให้ได้มูลค่ามากที่สุด โจทย์แบบนี้เรียกว่า fractional knapsack (knapsack แปลว่าเป้สะพายหลัง)

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

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

struct Item {
    long long weight, value;
};

int main()
{
    int n;
    long long capacity;
    cin >> n >> capacity;
    vector<Item> items(n);
    for (int i = 0; i < n; i++) {
        cin >> items[i].weight >> items[i].value;
    }
    sort(items.begin(), items.end(), [](const Item &a, const Item &b) {
        return a.value * b.weight > b.value * a.weight; // (1)!
    });
    double total = 0;
    long long room = capacity;
    for (int i = 0; i < n && room > 0; i++) {
        if (items[i].weight <= room) {
            total += items[i].value;
            room -= items[i].weight;
            cout << "take all " << items[i].weight << " kg\n";
        } else {
            total += (double)items[i].value * room / items[i].weight; // (2)!
            cout << "take " << room << " of " << items[i].weight << " kg\n";
            room = 0;
        }
    }
    cout << fixed << setprecision(2) << "value = " << total << '\n';
    return 0;
}

1. อยากเทียบ v_a / w_a > v_b / w_b แต่คูณ w_a w_b ทั้งสองข้างก่อน ได้การเทียบจำนวนเต็มล้วน ไม่มีเศษหายและไม่มีความคลาดของ double ผลคูณถึง 10¹⁸ ได้จึงเก็บเป็น long long
2. ตักแค่ room กิโลจาก weight กิโล ได้เงิน value × room / weight บาท แปลงเป็น double ก่อนคูณตามหน้า 1.4 ทศนิยมใช้แค่ตอนคำนวณคำตอบ ไม่ได้ใช้ตอนเรียง

4 20
8 200
9 100
5 150
6 96

take all 5 kg
take all 8 kg
take all 6 kg
take 1 of 9 kg
value = 457.11

ราคาต่อกิโลของสี่ชนิดคือ 25 11.11 30 และ 16 บาท ใส่ชนิด 30 บาทกับ 25 บาทครบ แล้วชนิด 16 บาท รวม 19 กิโล เหลือที่ว่าง 1 กิโล ตักชนิด 11.11 บาทมาหนึ่งกิโล ได้ 446 + 100/9 = 457.11 บาท เรียงเป็น O(N log N) ใส่อีก O(N)

ถ้าแบ่งไม่ได้ greedy ผิด

เปลี่ยนจากผลไม้ชั่งกิโลเป็นของที่แบ่งไม่ได้ เช่น ทุเรียนทั้งลูก ตู้เย็น หรือกล่องพัสดุ แต่ละชิ้นต้องเอาไปทั้งชิ้นหรือไม่เอาเลย เรียกว่า 0/1 knapsack ลองใช้ greedy เดิม เรียงตามราคาต่อกิโล หยิบชิ้นที่ยังใส่ได้ แล้วเทียบกับการลองทุกเซตแบบบทที่ 21

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

int n;
long long capacity;
vector<long long> weight, value;
long long best = 0;

void try_items(int k, long long used, long long total)
{
    if (k == n) {
        best = max(best, total);
        return;
    }
    try_items(k + 1, used, total);
    if (used + weight[k] <= capacity) {
        try_items(k + 1, used + weight[k], total + value[k]);
    }
}

int main()
{
    cin >> n >> capacity;
    weight.resize(n);
    value.resize(n);
    vector<int> order(n);
    for (int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
        order[i] = i;
    }
    sort(order.begin(), order.end(), [](int a, int b) {
        return value[a] * weight[b] > value[b] * weight[a];
    });
    long long room = capacity, greedy = 0;
    for (int i : order) {
        if (weight[i] <= room) {
            greedy += value[i];
            room -= weight[i];
        }
    }
    try_items(0, 0, 0);
    cout << "greedy = " << greedy << '\n';
    cout << "best = " << best << '\n';
    return 0;
}

3 10
6 30
5 20
5 20

greedy = 30
best = 40

รถรับได้ 10 กิโล ชิ้นแรกหนัก 6 กิโล 30 บาท คุ้มสุดที่กิโลละ 5 บาท greedy หยิบมาก่อน เหลือที่ 4 กิโล อีกสองชิ้นหนักชิ้นละ 5 กิโลใส่ไม่ได้ ได้ 30 บาท แต่เอาสองชิ้นหลังไปแทนได้ 40 บาท ที่ว่าง 4 กิโลที่เหลือทิ้งไว้ไม่ได้เงินเลย ราคาต่อกิโลที่ดีจึงไม่ได้แปลว่าคุ้มเมื่อแบ่งไม่ได้ เหตุผลแบบแลกหนึ่งกิโลใช้ไม่ได้อีกต่อไป เพราะแลกได้ทีละทั้งชิ้นเท่านั้น

ลองทำให้พัง

แบบที่ 1 หารจำนวนเต็มในฟังก์ชันเปรียบเทียบ

ในโปรแกรม fractional เขียนการเทียบตรงๆ ตามความหมาย เป็น

return a.value / a.weight > b.value / b.weight;

แล้วป้อนผลไม้สองชนิด ชนิดละ 10 กิโล ราคา 71 บาทกับ 79 บาท รถรับได้ 10 กิโล

2 10
10 71
10 79

take all 10 kg
value = 71.00

คำตอบที่ถูกคือ 79.00 ราคาต่อกิโลจริงคือ 7.1 กับ 7.9 แต่ long long หาร long long ตัดเศษทิ้งเหลือ 7 ทั้งคู่ ฟังก์ชันเปรียบเทียบจึงบอกว่าเท่ากัน และ sort ปล่อยให้ชนิดที่ถูกกว่ามาก่อน ไม่มีคำเตือน ตัวอย่างที่ราคาต่อกิโลเป็นจำนวนเต็มทุกตัวผ่านหมด ใช้การคูณไขว้แบบโปรแกรมต้นฉบับเสมอ ส่วน double ใช้ได้ถ้าเลขไม่ใหญ่ แต่สองชนิดที่ราคาต่อกิโลเท่ากันจริงอาจได้ทศนิยมคลาดกันเล็กน้อย

แบบที่ 2 ใช้ greedy กับของที่แบ่งไม่ได้

เป็นความผิดที่เจอบ่อยที่สุดของหน้านี้ และไม่มีอะไรเตือนเลย ตัวอย่างในโจทย์มักมีของไม่กี่ชิ้นที่ greedy บังเอิญได้คำตอบถูก โปรแกรม knapsack-01 ข้างบนแสดงแล้วว่าแค่สามชิ้นก็ผิดได้ ถ้าไม่แน่ใจว่าโจทย์เป็นแบบไหน ให้เทียบกับการลองทุกเซตบนข้อมูลเล็กๆ ตามวิธีในหน้า 23.5

สรุป

• เวลารอรวมน้อยสุด ทำงานที่สั้นที่สุดก่อน เพราะเวลาของคนหน้าคิวถูกนับซ้ำในทุกคนข้างหลัง
• ค่าสายมากสุดน้อยสุด ทำงานที่เส้นตายเร็วที่สุดก่อน โดยไม่สนเวลาที่ใช้
• พิสูจน์ทั้งสองแบบด้วยการสลับคู่ที่ติดกันที่ผิดลำดับ แล้วแสดงว่าไม่แย่ลง
• knapsack แบบแบ่งได้ เรียงตามราคาต่อหน่วยด้วยการคูณไขว้ ใส่จนเต็ม ชิ้นสุดท้ายตักบางส่วน
• knapsack แบบแบ่งไม่ได้ greedy ผิด ต้องใช้ dynamic programming ในบทที่ 24 และ 25
• ทุกแบบเป็น O(N log N) จากการเรียง