21.2 ทุกเซตย่อยและทุกลำดับ

ลูปซ้อนในหน้า 21.1 ใช้ได้เมื่อรู้ล่วงหน้าว่าจะเลือกกี่ชิ้น แต่โจทย์จำนวนมากให้เลือกกี่ชิ้นก็ได้ เช่น เลือกของรางวัลให้ใช้คูปองคุ้มที่สุด หรือให้จัดลำดับทั้งหมด เช่น ลำดับที่นั่งของเพื่อน N คน หน้า 9.5 เขียน recursion พิมพ์สตริงฐานสองทุกแบบและการเรียงสับเปลี่ยนทุกแบบไปแล้ว หน้านี้ใช้เครื่องมือที่สั้นกว่า คือไล่ทุกเซตย่อย (subset) ด้วยตัวเลขธรรมดาหนึ่งตัวที่เรียกว่า bitmask และไล่ทุกลำดับด้วย next_permutation จากบทที่ 16 ทั้งสองแบบไม่ต้องเขียน recursion เลย

ตัวเลขหนึ่งตัวแทนเซตย่อยหนึ่งชุด

ของ n ชิ้น แต่ละชิ้นเลือกหรือไม่เลือก ถ้าเขียน 1 แทนเลือก 0 แทนไม่เลือก เซตย่อยหนึ่งชุดก็คือสตริงฐานสองยาว n แบบในหน้า 9.5 และสตริงฐานสองก็คือตัวเลขในหน้า 12.3 นั่นเอง ให้ bit ที่ i ของตัวเลข (นับจากขวาสุดเป็น bit ที่ 0) บอกว่าเลือกชิ้นที่ i + 1 หรือไม่ ตัวเลข 0 ถึง 2ⁿ - 1 จึงแทนเซตย่อยทุกชุดพอดี ชุดละหนึ่งตัวเลข ไม่ขาดไม่ซ้ำ ตารางนี้คือของ 3 ชิ้น

ดูว่า mask เลือกชิ้นที่ i + 1 ไหม ก็คือดู bit ที่ i ด้วย (mask >> i) & 1 ตามตารางในหน้า 12.3 ส่วนจำนวนเซตย่อยทั้งหมด 2ⁿ เขียนเป็น 1 << n

เลือกของรางวัลให้ใช้คูปองคุ้มที่สุด

น้องได้คูปองแลกของรางวัลมูลค่า B บาท ใช้แลกของกี่ชิ้นก็ได้ แต่ราคารวมห้ามเกิน B และไม่ได้เงินทอน ร้านมีของ n ชิ้น ราคาไม่เท่ากัน ควรเลือกชิ้นไหนบ้างให้ราคารวมมากที่สุด

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

int main()
{
    int n;
    long long budget;
    cin >> n >> budget;
    vector<long long> price(n);
    for (int i = 0; i < n; i++) {
        cin >> price[i];
    }
    long long best = -1;
    int best_mask = 0;
    for (int mask = 0; mask < (1 << n); mask++) { // (1)!
        long long total = 0;
        for (int i = 0; i < n; i++) {
            if ((mask >> i) & 1) { // (2)!
                total += price[i];
            }
        }
        if (total <= budget && total > best) {
            best = total;
            best_mask = mask; // (3)!
        }
    }
    cout << "best " << best << '\n';
    cout << "items";
    for (int i = 0; i < n; i++) {
        if ((best_mask >> i) & 1) {
            cout << ' ' << i + 1;
        }
    }
    cout << '\n';
    cout << "count " << __builtin_popcount(best_mask) << '\n'; // (4)!
    return 0;
}

1. ไล่ทุกเซตย่อย ตั้งแต่ไม่เลือกอะไรเลย (0) ถึงเลือกทุกชิ้น (2ⁿ - 1) ใส่วงเล็บรอบ 1 << n ให้อ่านง่าย
2. bit ที่ i เป็น 1 แปลว่าเซตนี้เลือกชิ้นที่ i + 1 รวมราคาเฉพาะชิ้นที่เลือก ตรวจหนึ่งเซตใช้งาน O(n) ทั้งหมดจึงเป็น O(2ⁿ · n)
3. จำทั้งตัวเลข mask ไว้ ไม่ต้องจำเป็น vector ของชิ้นที่เลือก เพราะตัวเลขตัวเดียวบอกได้ครบว่าเลือกชิ้นไหนบ้าง
4. __builtin_popcount(x) นับว่า x มี bit ที่เป็น 1 กี่ตัว คือจำนวนชิ้นที่เลือก เป็นฟังก์ชันพิเศษของ GCC ใช้ได้ใน Code::Blocks และ grader ที่ใช้ GCC ทุกตัว ถ้า x เป็น long long ใช้ __builtin_popcountll

5 100
35 48 27 60 19

best 95
items 1 4
count 2

คำตอบคือชิ้นที่ 1 กับ 4 ราคา 35 + 60 = 95 ถ้าเลือกแบบโลภ คือหยิบชิ้นถูกก่อนให้ได้หลายชิ้น 19 + 27 + 35 = 81 แล้วหยิบชิ้นไหนต่อก็เกินงบ ได้แค่ 81 ส่วนหยิบชิ้นแพงก่อน 60 + 35 = 95 บังเอิญถูกกับข้อมูลชุดนี้ แต่ไม่ถูกเสมอ ลองทุกเซตย่อยไม่ต้องเดาว่ากฎไหนถูก เพราะดูครบทุกแบบแล้วจริงๆ

bitmask กับ recursion ในหน้า 9.5

สองวิธีไล่เซตย่อยครบ 2ⁿ ชุดเท่ากัน bitmask สั้นกว่า ไม่มีตัวแปร global และส่งเซตย่อยทั้งชุดไปไหนก็ได้เป็นตัวเลขตัวเดียว ส่วน recursion เลือกทีละชิ้น จึงรู้ผลรวมครึ่งทางและเลิกลองต่อได้ทันทีที่เกินงบ ซึ่งเป็นพื้นฐานของการตัดกิ่งในหน้า 21.4 bitmask ทำแบบนั้นไม่ได้ ต้องสร้างเซตให้ครบก่อนแล้วค่อยตรวจ

2ⁿ ไปได้แค่ไหน

รันโปรแกรม prizes กับราคาสุ่มและงบที่ใหญ่พอจะเลือกได้หลายชิ้น วัดบนเครื่องเดียวกับหน้า 21.1 แต่ละช่องคือค่ากลางของการรัน 5 ครั้ง

n = 20 สบาย พอถึง 24 ก็เกินหนึ่งวินาทีแล้ว ทุก n ที่เพิ่มหนึ่งทำให้งานเพิ่มเกินเท่าตัว เพราะทั้งจำนวนเซตเพิ่มเท่าตัว และแต่ละเซตต้องดูของเพิ่มอีกหนึ่งชิ้น 1 << n ที่เป็น int ใช้ได้ถึง n = 30 ซึ่งเลยขอบเขตที่ทันไปไกลแล้ว ไม่ต้องห่วงเรื่องล้น

ทุกลำดับด้วย next_permutation

เพื่อน n คนนั่งเรียงแถวเดียว คู่ที่สนิทกันถ้าได้นั่งติดกันจะคุยสนุก ให้คะแนนความสนุก h[i][j] ของคนที่ i กับ j เมื่อนั่งติดกัน ควรจัดลำดับที่นั่งแบบไหนให้คะแนนรวมของทุกคู่ที่นั่งติดกันมากที่สุด คำตอบหนึ่งแบบคือการเรียงสับเปลี่ยนของคน n คน ใช้ next_permutation ไล่ได้ครบตามที่เห็นในบทที่ 16

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

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> happy(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> happy[i][j];
        }
    }
    vector<int> seat(n);
    for (int i = 0; i < n; i++) {
        seat[i] = i; // (1)!
    }
    int best = -1;
    vector<int> best_seat;
    long long tried = 0;
    do {
        tried++;
        int total = 0;
        for (int i = 0; i + 1 < n; i++) {
            total += happy[seat[i]][seat[i + 1]]; // (2)!
        }
        if (total > best) {
            best = total;
            best_seat = seat; // (3)!
        }
    } while (next_permutation(seat.begin(), seat.end()));
    cout << "tried " << tried << '\n';
    cout << "best " << best << '\n';
    for (int i = 0; i < n; i++) {
        cout << best_seat[i] + 1 << (i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

1. ไล่ลำดับของหมายเลขคน 0 ถึง n - 1 ไม่ใช่ไล่ค่าในตาราง เริ่มจาก 0 1 2 ... ซึ่งเรียงแล้ว next_permutation จึงพาไปครบทุกลำดับ
2. seat[i] คือคนที่นั่งเก้าอี้ตัวที่ i คู่ที่ติดกันคือเก้าอี้ i กับ i + 1 ตรวจหนึ่งลำดับใช้งาน O(n) รวมเป็น O(n! · n)
3. กำหนด vector ให้กัน คัดลอกทั้งลำดับเก็บไว้ ถ้าเก็บแค่คะแนนจะไม่รู้ว่าลำดับไหนให้คะแนนนั้น

4
0 5 1 3
5 0 2 8
1 2 0 4
3 8 4 0

tried 24
best 17
1 2 4 3

ลองครบ 4! = 24 ลำดับ ดีที่สุดคือ 1 2 4 3 ได้ 5 + 8 + 4 = 17 ลำดับกลับหลัง 3 4 2 1 ก็ได้ 17 เท่ากัน แต่มาทีหลัง เงื่อนไข total > best ที่ใช้มากกว่าอย่างเดียว จึงเก็บลำดับที่เจอก่อนไว้ ถ้าโจทย์ให้ตอบลำดับที่น้อยที่สุดตามพจนานุกรม แบบนี้ได้คำตอบที่ต้องการพอดี

n! ไปได้แค่ไหน

รันโปรแกรม seating กับตารางคะแนนสุ่ม วัดบนเครื่องเดียวกัน ค่ากลางของ 3 ครั้ง

ตารางนี้มีสองเรื่องให้จำ เรื่องแรก n! โตเร็วกว่า 2ⁿ มาก ตารางนี้กับตารางของ prizes ข้างบนเป็นคนละโปรแกรม งานต่อแบบไม่เท่ากัน จึงเทียบที่การโตเมื่อ n เพิ่ม ไม่ใช่เทียบเวลาช่องต่อช่อง เพิ่ม n หนึ่งงานเพิ่มราว n เท่า 11 ยังทันแบบ -O2 แต่ 12 ไม่ทันแล้ว เรื่องที่สอง ตั้งแต่ n = 10 แบบ Code::Blocks ช้ากว่าแบบ -O2 ราว 10 ถึง 23 เท่า เพราะ vector กับ next_permutation เป็นโค้ดของ STL ที่เขียนไว้ให้ compiler ปรับ ถ้าไม่เปิด -O2 ทุกการเข้าถึงช่องของ vector กลายเป็นการเรียกฟังก์ชันจริงๆ grader ส่วนใหญ่คอมไพล์ด้วย -O2 จะวัดว่าโปรแกรมที่ใช้ STL ทันไหม ให้วัดแบบ -O2

ลองทำให้พัง

ตรวจ bit ด้วย == 1

ในโปรแกรม prizes เปลี่ยนการตรวจ bit ทั้งสองจุด จาก (mask >> i) & 1 เป็นแบบนี้ ซึ่งดูเหมือนจะแปลว่าเหมือนกัน

if ((mask & (1 << i)) == 1) {

คอมไพล์ผ่านโดยไม่มีคำเตือนแม้เปิด -Wall -Wextra ป้อนข้อมูลชุดเดิมได้

best 35
items 1
count 1

mask & (1 << i) ไม่ได้ให้ 0 หรือ 1 แต่ให้ 0 หรือ 1 << i เช่น ถ้า bit ที่ 3 เป็น 1 จะได้ 8 ซึ่งไม่เท่ากับ 1 เงื่อนไขจึงจริงได้แค่ตอน i = 0 โปรแกรมเลยมองไม่เห็นชิ้นที่ 2 เป็นต้นไปเลย ได้คำตอบแค่ชิ้นแรก แก้ได้สองทาง ใช้ (mask >> i) & 1 ที่ได้ 0 หรือ 1 จริงๆ หรือเทียบกับ 0 แทน คือ (mask & (1 << i)) != 0

สรุป

• เซตย่อยของ n ชิ้นแทนด้วยตัวเลข 0 ถึง 2ⁿ - 1 bit ที่ i บอกว่าเลือกชิ้นที่ i + 1 หรือไม่ ไล่ด้วย for (mask = 0; mask < (1 << n); mask++)
• ตรวจ bit ด้วย (mask >> i) & 1 นับจำนวนชิ้นที่เลือกด้วย __builtin_popcount
• ลองทุกเซตย่อยเป็น O(2ⁿ · n) n = 20 สบาย n = 24 เริ่มเกินหนึ่งวินาที
• ทุกลำดับใช้ next_permutation กับ vector ของหมายเลข 0 ถึง n - 1 ที่เรียงแล้ว เป็น O(n! · n) n = 11 ยังทันแบบ -O2
• โปรแกรมที่ใช้ STL ให้วัดเวลาแบบ -O2 เพราะแบบ Code::Blocks ช้ากว่าหลายเท่า