25.1 0/1 knapsack และ unbounded knapsack

น้องจะไปเข้าค่ายพักแรม กระเป๋าแบกได้ไม่เกิน W กิโลกรัม มีของให้เลือก N ชิ้น แต่ละชิ้นมีน้ำหนักกับความจำเป็นเป็นคะแนน ควรหยิบชิ้นไหนไปบ้างให้คะแนนรวมมากที่สุด โจทย์แบบนี้ชื่อ knapsack (เป้) เป็นโจทย์ DP ที่ค่าย 2 สอนทุกปี และซ่อนอยู่ในโจทย์ TOI หลายข้อในรูปของงบประมาณ เวลา หรือพื้นที่ที่มีจำกัด หน้านี้สร้างตารางสองมิติตามวิธีคิดในบทที่ 24 แล้วลดเหลือแถวเดียว จุดที่ต้องเข้าใจให้ได้คือทำไมแถวเดียวต้องวนถอยหลัง เพราะถ้าวนเดินหน้าจะได้โจทย์อีกแบบหนึ่งทันที

โจทย์และทำไม greedy ไม่พอ

ของ 4 ชิ้น กระเป๋าจุ 7 กิโลกรัม แต่ละชิ้นหยิบได้ครั้งเดียว จะหยิบหรือไม่หยิบ จึงเรียกว่า 0/1 knapsack

ถ้าใช้ greedy แบบบทที่ 23 หยิบชิ้นที่คะแนนต่อกิโลกรัมสูงก่อน จะได้ชิ้นที่ 1 กับชิ้นที่ 2 หนักรวม 4 กิโลกรัม ชิ้นที่ 3 ใส่แล้วเป็น 8 เกิน ชิ้นที่ 4 ก็เกิน ได้คะแนน 55 แต่ถ้าทิ้งชิ้นที่ 1 แล้วหยิบชิ้นที่ 2 กับ 3 จะหนักพอดี 7 กิโลกรัม ได้ 90 คะแนน greedy พลาดเพราะชิ้นที่ดูคุ้มที่สุดกินที่ไปหนึ่งกิโลกรัม ทำให้ใส่ชุดที่ดีกว่าไม่ลง

วิธีที่ถูกแน่นอนคือลองทุกชุด แบบ backtracking ในบทที่ 21 ของแต่ละชิ้นมีสองทาง หยิบหรือไม่หยิบ

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

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

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

int main()
{
    cin >> n >> capacity;
    weight.resize(n);
    value.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
    }
    try_items(0, 0, 0);
    cout << best_value << '\n';
    return 0;
}

4 7
1 15
3 40
4 50
5 60

90

ถูกต้อง แต่ N ชิ้นมี 2^N ชุด 30 ชิ้นก็เกินพันล้านชุดแล้ว ต้องหาส่วนที่ซ้ำกันมาจำไว้แทน

ตารางสองมิติ

สังเกตว่าหลังตัดสินใจเรื่องของ i ชิ้นแรกไปแล้ว สิ่งเดียวที่มีผลกับของที่เหลือคือ น้ำหนักที่ยังเหลือในกระเป๋า ไม่สำคัญว่าหยิบชิ้นไหนมาถึงตรงนี้ ทำตามวิธีคิด DP สี่ขั้นในหน้า 24.2 ได้ดังนี้

• นิยามสถานะ best[i][c] คือคะแนนมากที่สุดเมื่อเลือกได้เฉพาะของ i ชิ้นแรก และน้ำหนักรวมไม่เกิน c
• หาความสัมพันธ์ ดูของชิ้นที่ i ชิ้นเดียว ถ้าไม่หยิบ ได้เท่ากับ best[i - 1][c] ถ้าหยิบ (ต้องมี c >= w[i]) กระเป๋าเหลือที่ c - w[i] ให้ของ i - 1 ชิ้นแรก ได้ best[i - 1][c - w[i]] + v[i] เลือกทางที่มากกว่า
• กรณีฐาน ยังไม่มีของให้เลือกเลย best[0][c] = 0 ทุก c
• ลำดับการเติมและคำตอบสุดท้าย แถว i ใช้แค่แถว i - 1 จึงเติมทีละแถวจากบนลงล่าง คำตอบอยู่ที่ best[N][W]

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

int main()
{
    int n, capacity;
    cin >> n >> capacity;
    vector<int> weight(n + 1), value(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }
    vector<vector<int>> best(n + 1, vector<int>(capacity + 1, 0)); // (1)!
    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= capacity; c++) {
            best[i][c] = best[i - 1][c]; // (2)!
            if (c >= weight[i]) {
                best[i][c] = max(best[i][c], best[i - 1][c - weight[i]] + value[i]); // (3)!
            }
        }
    }
    for (int i = 0; i <= n; i++) {
        cout << "i=" << i << ":";
        for (int c = 0; c <= capacity; c++) {
            cout << setw(4) << best[i][c]; // (4)!
        }
        cout << '\n';
    }
    cout << "best value = " << best[n][capacity] << '\n';
    int c = capacity;
    cout << "take items:";
    for (int i = n; i >= 1; i--) {
        if (best[i][c] != best[i - 1][c]) { // (5)!
            cout << ' ' << i;
            c -= weight[i];
        }
    }
    cout << '\n';
    return 0;
}

1. สร้างทั้งตารางเป็น 0 ไว้ก่อน แถว 0 จึงเป็นค่าเริ่มต้นที่ถูกอยู่แล้ว
2. ทางที่ไม่หยิบชิ้นที่ i ใส่ไว้ก่อน แล้วค่อยเทียบกับทางที่หยิบ
3. หยิบชิ้นที่ i ต้องมาจากแถว i - 1 เท่านั้น เพราะชิ้นที่ i หยิบได้ครั้งเดียว
4. setw(4) อยู่ในไฟล์ iomanip เดียวกับ setprecision ในหน้า 15.2 สั่งให้ตัวที่พิมพ์ถัดไปกินที่ 4 ตัวอักษร ถ้าสั้นกว่านั้นจะเติมช่องว่างข้างหน้า คอลัมน์ของตารางจึงตรงกัน มีผลกับตัวถัดไปตัวเดียว จึงต้องใส่ทุกครั้งที่พิมพ์
5. ค่าเปลี่ยนจากแถวบน แปลว่าคำตอบที่ดีที่สุดของช่องนี้ต้องหยิบชิ้นที่ i ถ้าเท่ากัน ไม่หยิบก็ได้ค่าเท่าเดิม

4 7
1 15
3 40
4 50
5 60

i=0:   0   0   0   0   0   0   0   0
i=1:   0  15  15  15  15  15  15  15
i=2:   0  15  15  40  55  55  55  55
i=3:   0  15  15  40  55  65  65  90
i=4:   0  15  15  40  55  65  75  90
best value = 90
take items: 3 2

อ่านตารางทีละช่อง ช่องแถว 3 คอลัมน์ 7 คือ 90 มาจากการเทียบสองทาง ไม่หยิบชิ้นที่ 3 ได้ช่องบนคือ 55 หยิบชิ้นที่ 3 ที่หนัก 4 กิโลกรัม ต้องดูช่องแถว 2 คอลัมน์ 3 ซึ่งเป็น 40 รวมเป็น 40 + 50 = 90 มากกว่า จึงได้ 90 คำตอบอยู่ที่ช่องขวาล่าง

ส่วนท้ายของโปรแกรมย้อนรอยหาว่าหยิบชิ้นไหน แบบการเก็บเส้นทางย้อนกลับในบทที่ 24 เริ่มที่ช่องคำตอบ best[4][7] = 90 เท่ากับช่องบน จึงไม่ได้หยิบชิ้นที่ 4 ขึ้นไปแถว 3 ได้ 90 แต่ช่องบนเป็น 55 จึงหยิบชิ้นที่ 3 ลดน้ำหนักเหลือ 3 แล้วดูแถว 2 คอลัมน์ 3 เป็น 40 ช่องบนเป็น 15 จึงหยิบชิ้นที่ 2 เหลือ 0 ชิ้นที่ 1 ไม่ได้หยิบ

ตารางมี (N + 1)(W + 1) ช่อง แต่ละช่องใช้เวลาคงที่ จึงเป็น O(NW) ทั้งเวลาและหน่วยความจำ ถ้า N = 100 และ W = 100000 คือราว 10⁷ ช่อง เป็น int ราว 40 MB เวลาสบาย แต่หน่วยความจำเริ่มเยอะ ส่วนถัดไปลดให้เหลือแถวเดียว

เหลือแถวเดียว วนถอยหลัง

แถว i ใช้แค่แถว i - 1 ไม่เคยย้อนไปดูแถวที่เก่ากว่านั้น จึงเก็บแถวเดียวแล้วเขียนทับไปเรื่อยๆ ได้ ก่อนเริ่มของชิ้นที่ i อาเรย์ best คือแถว i - 1 พอทำชิ้นที่ i เสร็จก็กลายเป็นแถว i แต่ระหว่างที่กำลังเขียนทับ อาเรย์มีค่าของสองแถวปนกัน และนี่คือที่มาของกฎสำคัญ

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

int main()
{
    int n, capacity;
    cin >> n >> capacity;
    vector<int> best(capacity + 1, 0);
    for (int i = 1; i <= n; i++) {
        int weight, value;
        cin >> weight >> value;
        for (int c = capacity; c >= weight; c--) { // (1)!
            best[c] = max(best[c], best[c - weight] + value);
        }
        cout << "after item " << i << ":";
        for (int c = 0; c <= capacity; c++) {
            cout << setw(4) << best[c];
        }
        cout << '\n';
    }
    cout << "best value = " << best[capacity] << '\n';
    return 0;
}

1. วนจาก capacity ลงมาถึง weight ช่องที่น้อยกว่า weight หยิบชิ้นนี้ไม่ได้ ค่าเท่าแถวบนอยู่แล้ว จึงไม่ต้องแตะ

4 7
1 15
3 40
4 50
5 60

after item 1:   0  15  15  15  15  15  15  15
after item 2:   0  15  15  40  55  55  55  55
after item 3:   0  15  15  40  55  65  65  90
after item 4:   0  15  15  40  55  65  75  90
best value = 90

ทุกบรรทัดตรงกับแถวของตารางสองมิติ ตอนคำนวณ best[c] ต้องใช้ best[c - weight] ของ แถวบน เมื่อวนถอยหลัง ช่อง c - weight อยู่ทางซ้าย ยังไม่ถูกเขียนทับในรอบนี้ จึงยังเป็นค่าของแถวบนจริง หน่วยความจำลดจาก O(NW) เหลือ O(W) เวลายังเป็น O(NW) เท่าเดิม

วนเดินหน้าแล้วผิดเพราะอะไร

เปลี่ยนลูปเป็น for (int c = weight; c <= capacity; c++) ส่วนอื่นเหมือนเดิมทุกตัวอักษร

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

int main()
{
    int n, capacity;
    cin >> n >> capacity;
    vector<int> best(capacity + 1, 0);
    for (int i = 1; i <= n; i++) {
        int weight, value;
        cin >> weight >> value;
        for (int c = weight; c <= capacity; c++) {
            best[c] = max(best[c], best[c - weight] + value);
        }
        cout << "after item " << i << ":";
        for (int c = 0; c <= capacity; c++) {
            cout << setw(4) << best[c];
        }
        cout << '\n';
    }
    cout << "best value = " << best[capacity] << '\n';
    return 0;
}

4 7
1 15
3 40
4 50
5 60

after item 1:   0  15  30  45  60  75  90 105
after item 2:   0  15  30  45  60  75  90 105
after item 3:   0  15  30  45  60  75  90 105
after item 4:   0  15  30  45  60  75  90 105
best value = 105

ได้ 105 ซึ่งเป็นไปไม่ได้ ของสี่ชิ้นรวมกันหนัก 13 กิโลกรัม ใส่ได้ไม่เกิน 7 และ 90 คือดีที่สุดแล้ว ดูของชิ้นที่ 1 ที่หนัก 1 กิโลกรัม ได้ 15 คะแนน ทีละช่อง

เมื่อวนเดินหน้า ช่องทางซ้ายถูกเขียนทับในรอบนี้ไปก่อนแล้ว best[c - weight] จึงเป็นค่าของ แถวเดียวกัน ซึ่งอาจรวมชิ้นนี้ไว้แล้ว ใส่ซ้ำอีกก็คือหยิบชิ้นเดิมหลายครั้ง สุดท้ายได้ชิ้นที่ 1 เจ็ดชิ้น 7 × 15 = 105 ชิ้นอื่นสู้ไม่ได้ ทุกแถวจึงเหมือนกันหมด

unbounded knapsack

ความผิดเมื่อกี้กลายเป็นคำตอบที่ถูกของอีกโจทย์ ร้านขนมจัดกล่องของขวัญที่ใส่ได้ไม่เกิน 10 ช่อง มีขนม 3 แบบ แต่ละแบบมีกี่ชิ้นก็ได้ แบบแรกใช้ 3 ช่อง ขาย 50 บาท แบบที่สองใช้ 4 ช่อง ขาย 70 บาท แบบที่สามใช้ 5 ช่อง ขาย 80 บาท จัดยังไงให้กล่องราคาสูงที่สุด ของแต่ละแบบหยิบซ้ำได้ไม่จำกัด เรียกว่า unbounded knapsack

ถ้าคิดเป็นตาราง ตอนหยิบแบบที่ i แล้ว ยังหยิบแบบที่ i ซ้ำได้อีก สูตรจึงมาจาก แถวเดียวกัน best[i][c - w[i]] + v[i] ซึ่งตรงกับการวนเดินหน้าในแถวเดียวพอดี

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

int main()
{
    int n, capacity;
    cin >> n >> capacity;
    vector<int> best(capacity + 1, 0);
    for (int i = 1; i <= n; i++) {
        int weight, value;
        cin >> weight >> value;
        for (int c = weight; c <= capacity; c++) {
            best[c] = max(best[c], best[c - weight] + value);
        }
    }
    for (int c = 0; c <= capacity; c++) {
        cout << best[c] << (c == capacity ? '\n' : ' ');
    }
    cout << "best value = " << best[capacity] << '\n';
    return 0;
}

3 10
3 50
4 70
5 80

0 0 0 50 70 80 100 120 140 150 170
best value = 170

170 บาทได้จากแบบแรกสองชิ้นกับแบบที่สองหนึ่งชิ้น ใช้ 3 + 3 + 4 = 10 ช่องพอดี ถ้าใส่แบบที่สามสองชิ้นได้แค่ 160 ความต่างของสองโจทย์อยู่ที่ทิศของลูปบรรทัดเดียว

โปรแกรม count-sets ที่นับวิธีทอนเหรียญในหน้า 24.3 ก็คือ unbounded knapsack ที่เปลี่ยนจากหาค่ามากสุดเป็นการนับ เหรียญแต่ละชนิดใช้ซ้ำได้ ลูปในจึงเดินหน้าเหมือนกัน ส่วนลองทำให้พังของหน้านั้นที่กลับลูปเป็นถอยหลังแล้วได้คำตอบของเหรียญชนิดละเหรียญเดียว ก็คือ 0/1 knapsack ในหน้านี้

เร็วขึ้นแค่ไหน

วัดบนเครื่องเดียวกับหน้า 19.1 คือโน้ตบุ๊ก AMD Ryzen AI 9 HX 370 Windows 11 และ GCC 14.2 ของ Code::Blocks ของแต่ละชิ้นหนักสุ่ม 1 ถึง 1000 คะแนนสุ่ม 1 ถึง 1000 กระเป๋าจุครึ่งหนึ่งของน้ำหนักรวม วิธีลองทุกชุดคือโปรแกรม knapsack-brute ข้างบน วิธี DP คือโปรแกรม knapsack-one-row ที่ตัดส่วนพิมพ์ตารางออก และเก็บคะแนนเป็น long long รันแต่ละแบบ 5 รอบ ตารางเป็นค่ากลาง

ลองทุกชุดช้าลงราวสิบถึงยี่สิบเท่าทุกครั้งที่ของเพิ่มสี่ชิ้น ใกล้กับ 2⁴ = 16 ที่คาดไว้ ส่วน DP ที่ N = 32 เติมแค่ราว 2.6 × 10⁵ ช่อง เวลาเกือบทั้งหมดคือการเปิดโปรแกรมกับอ่านข้อมูล แม้ของร้อยชิ้นกับกระเป๋าแสนกิโลกรัม ซึ่งเป็น 10⁷ ช่อง ก็ยังไม่ถึงหนึ่งในสิบวินาที

ลองทำให้พัง

แบบที่ 1 ประกาศตารางใหญ่ไว้ใน main

เขียนตารางสองมิติเป็นอาเรย์ธรรมดาให้รองรับ N = 100 กับ W = 100000 แบบนี้

int main()
{
    int n, capacity;
    cin >> n >> capacity;
    int best[101][100001];

คอมไพล์ผ่านโดยไม่มีคำเตือน แต่รันกับข้อมูลเข้าชุดสี่ชิ้นข้างบน โปรแกรมปิดตัวทันทีโดยไม่พิมพ์อะไร Code::Blocks ขึ้นว่า

Process returned -1073741571 (0xC00000FD)

0xC00000FD คือรหัสของ Windows ที่แปลว่า stack overflow ตัวแปรใน main ใช้ได้รวมราว 2 MB แต่ตารางนี้ใช้ 101 × 100001 × 4 byte ราว 40 MB พังทันทีที่เข้า main แม้ข้อมูลจริงจะมีแค่สี่ชิ้น grader จะให้ผลว่า runtime error แก้ได้สองทาง ใช้ vector แบบโปรแกรม knapsack-table ซึ่งจองตามขนาดจริง หรือย้ายอาเรย์ไปประกาศนอก main ซึ่งไม่ถูกจำกัดแบบนี้ ทางที่ดีกว่าคือใช้แถวเดียว ซึ่งเหลือแค่ราว 400 KB

แบบที่ 2 ลูปผิดทิศ

เป็นความผิดที่เห็นไปแล้วในหัวข้อวนเดินหน้า แต่อยากให้จำเป็นกฎ เพราะ compiler ไม่เตือน และกับข้อมูลบางชุดก็ได้คำตอบถูกโดยบังเอิญ เช่น ของทุกชิ้นหนักกว่าครึ่งหนึ่งของกระเป๋า จะหยิบซ้ำไม่ลงอยู่แล้ว ทุกครั้งที่เขียน knapsack แถวเดียว ให้ถามตัวเองว่าของแต่ละชิ้นหยิบซ้ำได้ไหม แล้วทดสอบด้วยของชิ้นเดียวที่เบากว่ากระเป๋ามาก เช่น 1 7 กับ 1 15 คำตอบที่ถูกคือ 15 ถ้าได้ 105 แปลว่าทิศผิด

สรุป

• best[i][c] คือคะแนนมากสุดจากของ i ชิ้นแรกที่หนักไม่เกิน c ได้จากไม่หยิบ best[i - 1][c] หรือหยิบ best[i - 1][c - w] + v
• เวลา O(NW) ซึ่ง W คือค่าของตัวเลข ถ้า W ใหญ่มากต้องเปลี่ยนมิติของตาราง
• ย้อนรอยหาว่าหยิบชิ้นไหน ด้วยการเทียบช่องกับช่องแถวบน
• แถวเดียวใช้หน่วยความจำ O(W) 0/1 knapsack วนถอยหลัง unbounded knapsack วนเดินหน้า
• ตารางใหญ่ห้ามประกาศเป็นอาเรย์ใน main ใช้ vector หรือประกาศนอก main