24.3 ทอนเหรียญ น้อยที่สุดและนับวิธี

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

ใช้น้อยที่สุด เมื่อบางจำนวนทำไม่ได้

ไปรษณีย์มีแสตมป์ N แบบ ราคาดวงละ p₁ ถึง p_N บาท มีแบบละกี่ดวงก็ได้ ต้องติดแสตมป์บนซองให้ราคารวมพอดี X บาท ใช้น้อยดวงที่สุด หน้า 24.1 มีเหรียญ 1 บาทเสมอจึงทอนได้ทุกจำนวน แต่ถ้ามีแค่แสตมป์ 5 กับ 7 บาท ราคา 23 บาททำไม่ได้เลย

1. สถานะ fewest[x] คือจำนวนดวงน้อยที่สุดที่ราคารวมพอดี x บาท ถ้าทำไม่ได้ให้เป็นค่าพิเศษ INF (infinity แปลว่าอนันต์)
2. ความสัมพันธ์ ดวงที่ติดดวงสุดท้ายราคา p ใดก็ได้ที่ไม่เกิน x ได้ fewest[x] = min(fewest[x - p] + 1) ทุก p
3. กรณีฐาน fewest[0] = 0 ส่วนช่องอื่นเริ่มที่ INF แปลว่ายังไม่เจอวิธี
4. เติม x จาก 1 ถึง X ถ้า fewest[X] ยังเป็น INF แปลว่าทำไม่ได้

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

const int INF = 1000000000; // (1)!

int main()
{
    int n, target;
    cin >> n >> target;
    vector<int> prices(n);
    for (int i = 0; i < n; i++) {
        cin >> prices[i];
    }
    vector<int> fewest(target + 1, INF);
    fewest[0] = 0;
    for (int x = 1; x <= target; x++) {
        for (int p : prices) {
            if (p <= x) {
                fewest[x] = min(fewest[x], fewest[x - p] + 1); // (2)!
            }
        }
    }
    for (int x = 0; x <= target; x++) {
        if (fewest[x] == INF) { // (3)!
            cout << '-';
        } else {
            cout << fewest[x];
        }
        cout << (x < target ? ' ' : '\n');
    }
    return 0;
}

1. เลือก INF ให้มากกว่าคำตอบจริงทุกค่า แต่บวกหนึ่งแล้วยังไม่ล้น int ห้ามใช้ INT_MAX ดูในส่วนลองทำให้พัง
2. ถ้า fewest[x - p] เป็น INF ค่า INF + 1 ก็ไม่มีทางชนะค่าอื่น ช่อง x จึงยังเป็น INF ต่อไปเอง ไม่ต้องเขียน if แยก
3. พิมพ์ - ตรงจำนวนที่ทำไม่ได้ ให้อ่านง่าย

2 24
5 7

0 - - - - 1 - 1 - - 2 - 2 - 2 3 - 3 - 3 4 3 4 - 4

อ่านจากซ้ายเป็นราคา 0 ถึง 24 บาท 23 บาททำไม่ได้ 24 บาทใช้ 4 ดวงคือ 5 + 5 + 7 + 7 ส่วน 21 บาทใช้ 3 ดวงคือ 7 สามดวง แม้ 20 บาทจะใช้ 4 ดวง ค่าในตารางจึงไม่ได้เพิ่มตามราคาเสมอไป greedy ที่หยิบดวงแพงก่อนจะตันที่ 24 บาท เพราะ 7 + 7 + 7 แล้วเหลือ 3 บาท ทั้งที่ทำได้ด้วย 4 ดวง เวลาเป็น O(XN) ตามหลักจำนวนสถานะคูณงานต่อสถานะ

นับจำนวนวิธี สองคำถามที่ต่างกัน

มีเหรียญ 1 2 และ 5 บาท ต้องจ่าย 5 บาท มีกี่วิธี คำตอบขึ้นกับว่าถือว่า 1 + 2 + 2 กับ 2 + 1 + 2 ต่างกันไหม

• ลำดับสำคัญ เช่น หยอดเหรียญเข้าตู้ทีละเหรียญ แล้วตู้บันทึกลำดับไว้ 1 + 2 + 2 กับ 2 + 1 + 2 เป็นคนละวิธี นับแบบนี้เรียกว่านับแบบเรียงสับเปลี่ยน (permutation) ได้ 9 วิธี
• ลำดับไม่สำคัญ เช่น ยื่นเหรียญเป็นกำมือเดียว สนแค่ว่าใช้เหรียญอะไรกี่เหรียญ นับแบบนี้เรียกว่านับแบบจัดหมู่ (combination) ได้ 4 วิธี คือ 5, 2+2+1, 2+1+1+1 และ 1+1+1+1+1

ลำดับสำคัญ ลูปนอกเป็นจำนวนเงิน

สถานะ ways[x] คือจำนวนลำดับการหยอดที่รวมได้ x บาท เหรียญสุดท้ายที่หยอดเป็นเหรียญไหนก็ได้ จึงเป็นโครงเดียวกับบันไดในหน้า 24.2 ที่ก้าวได้หลายขนาด ways[x] = ผลรวมของ ways[x - c] ทุกเหรียญ c

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

const int MOD = 1000000007;

int main()
{
    int n, target;
    cin >> n >> target;
    vector<int> coins(n);
    for (int i = 0; i < n; i++) {
        cin >> coins[i];
    }
    vector<int> ways(target + 1, 0);
    ways[0] = 1;
    for (int x = 1; x <= target; x++) { // (1)!
        for (int c : coins) { // (2)!
            if (c <= x) {
                ways[x] = (ways[x] + ways[x - c]) % MOD;
            }
        }
    }
    for (int x = 0; x <= target; x++) {
        cout << ways[x] << (x < target ? ' ' : '\n');
    }
    return 0;
}

1. ลูปนอกคือจำนวนเงิน ช่อง x เติมเสร็จในรอบเดียว
2. ลูปในลองทุกเหรียญเป็นเหรียญสุดท้าย ทุกเหรียญมีโอกาสมาหลังเหรียญอื่น ลำดับที่ต่างกันจึงถูกนับแยกกัน

3 5
1 2 5

1 1 2 3 5 9

ช่อง 3 ได้ 3 คือ 1+1+1, 1+2 และ 2+1 ช่อง 5 ได้ 9 ซึ่งรวม 5 บาทเหรียญเดียวกับอีกแปดลำดับของเหรียญ 1 กับ 2 ตัวเลขโตเร็วมาก ป้อน 1000 บาทกับเหรียญ 1 2 5 10 ตัวเลขท้ายสุดคือ 329088431 ซึ่งเป็นเศษแล้ว เพราะคำตอบจริงยาวกว่าสองร้อยหลัก

ลำดับไม่สำคัญ ลูปนอกเป็นเหรียญ

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

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

const int MOD = 1000000007;

int main()
{
    int n, target;
    cin >> n >> target;
    vector<int> coins(n);
    for (int i = 0; i < n; i++) {
        cin >> coins[i];
    }
    vector<int> ways(target + 1, 0);
    ways[0] = 1;
    for (int c : coins) { // (1)!
        for (int x = c; x <= target; x++) { // (2)!
            ways[x] = (ways[x] + ways[x - c]) % MOD;
        }
        for (int x = 0; x <= target; x++) { // (3)!
            cout << ways[x] << (x < target ? ' ' : '\n');
        }
    }
    return 0;
}

1. ลูปนอกคือชนิดเหรียญ ทีละชนิดตามลำดับ
2. เริ่มที่ x = c เพราะจำนวนที่น้อยกว่า c ใช้เหรียญนี้ไม่ได้ เติมจากน้อยไปมาก ways[x - c] จึงรวมวิธีที่ใช้เหรียญ c ไปแล้วด้วย ใช้เหรียญเดิมซ้ำได้หลายเหรียญ
3. พิมพ์ตารางหลังจบเหรียญแต่ละชนิด เพื่อดูว่าค่าเปลี่ยนยังไง

3 5
1 2 5

1 1 1 1 1 1
1 1 2 2 3 3
1 1 2 2 3 4

หลังเหรียญ 1 บาท ทุกจำนวนมีวิธีเดียวคือ 1 บาทล้วน หลังเหรียญ 2 บาท ช่อง 4 ได้ 3 คือ 1+1+1+1, 2+1+1 และ 2+2 หลังเหรียญ 5 บาท มีแค่ช่อง 5 ที่เพิ่มขึ้นหนึ่งวิธี ได้ 4 ตรงกับที่นับไว้ ความหมายของ ways[x] ระหว่างทางคือ จำนวนวิธีรวมได้ x บาท โดยใช้เฉพาะเหรียญชนิดที่ผ่านลูปนอกมาแล้ว ป้อน 1000 บาทกับเหรียญ 1 2 5 10 ได้ 1712051 วิธี ซึ่งน้อยกว่าแบบลำดับสำคัญมาก

สองโปรแกรมมีบรรทัดในลูปเหมือนกันทุกตัวอักษร ต่างกันแค่ลำดับของลูป อ่านโจทย์ให้ออกก่อนว่าถามแบบไหน คำว่า "ลำดับต่างกันถือว่าต่างกัน" หรือ "ลำดับการหยอด" คือแบบแรก คำว่า "ชุด" "กลุ่ม" หรือ "ใช้เหรียญอะไรบ้าง" คือแบบที่สอง ทั้งสองแบบเป็น O(XK) เมื่อ K คือจำนวนชนิดเหรียญ

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

วิธีตรงไปตรงมาของการนับแบบลำดับสำคัญคือ recursion ที่ลองทุกเหรียญเป็นเหรียญถัดไปโดยไม่จด ใช้เหรียญ 1 2 5 10 วัดบนเครื่องเดียวกับหน้า 24.1 รันแบบละ 5 ครั้ง ยกเว้นแถว 40 บาทที่รัน 3 ครั้ง แบบตารางใช้ mod ส่วนแบบ recursion ไม่ใช้ เพราะคำตอบยังไม่เกิน long long

recursion ที่เงิน 40 บาทนับได้ 1255304727 วิธี ซึ่งต้องเรียกตัวเองมากกว่าจำนวนวิธีนั้นอีก จึงรอเป็นนาที ส่วนตารางทั้งสองแบบทำงานราว 4 × 10⁷ ขั้นที่เงินสิบล้านบาท แบบลำดับไม่สำคัญเร็วกว่าราว 2 ถึง 3 เท่า เพราะลูปในไม่ต้องเช็ก c <= x

ลองทำให้พัง

แบบที่ 1 ใช้ INT_MAX เป็น INF

ในโปรแกรม stamps คิดว่า INF ควรเป็นค่าที่ใหญ่ที่สุดจริงๆ จึงเปลี่ยนเป็น const int INF = INT_MAX; ป้อนข้อมูลเข้าเดิม บนเครื่องที่เขียนเอกสารนี้ได้

0 - - - - 1 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483647 -2147483647 -2147483647 -2147483647 -2147483647 -2147483647 -2147483647 -2147483646 -2147483646 -2147483646 -2147483646 -2147483646 -2147483646

ตอนเติมช่อง 6 โปรแกรมลองแสตมป์ 5 บาท อ่าน fewest[1] ซึ่งเป็น INT_MAX บวกหนึ่งแล้วล้นเป็นค่าติดลบที่น้อยที่สุดตามหน้า 1.3 ค่าติดลบชนะทุกค่าใน min แล้วลามไปทุกช่องที่อ่านต่อจากมัน ใช้ INF ที่มีที่ว่างเหลือ เช่น 10⁹ ซึ่งบวกหนึ่งหรือบวกกันสองค่าก็ยังไม่ล้น หรือเช็ก fewest[x - p] != INF ก่อนบวก

แบบที่ 2 ลูปจำนวนเงินจากมากไปน้อย

ในโปรแกรม count-sets เปลี่ยนลูปในเป็น for (int x = target; x >= c; x--) ป้อนข้อมูลเข้าเดิม

1 1 0 0 0 0
1 1 1 1 0 0
1 1 1 1 0 1

ช่อง 5 ได้ 1 ช่อง 4 ได้ 0 เพราะตอนเติมช่อง x ช่อง x - c ยังเป็นค่าก่อนเจอเหรียญ c ทุกวิธีจึงใช้เหรียญแต่ละชนิดได้ไม่เกินหนึ่งเหรียญ เหลือแค่ 5 บาทเหรียญเดียว นี่เป็นคำตอบของคำถามอื่น คือ "มีเหรียญชนิดละเหรียญเดียว" ซึ่งเป็นเรื่องของ knapsack ในบทที่ 25 ทิศของลูปจึงเป็นส่วนหนึ่งของความหมาย ไม่ใช่แค่ความชอบ

สรุป

• จำนวนที่ทำไม่ได้ใช้ค่า INF ที่บวกหนึ่งแล้วไม่ล้น เช่น 10⁹ แล้วเช็กตอนท้ายว่าคำตอบยังเป็น INF ไหม
• นับแบบลำดับสำคัญ ลูปนอกเป็นจำนวนเงิน ลูปในเป็นเหรียญ
• นับแบบลำดับไม่สำคัญ ลูปนอกเป็นเหรียญ ลูปในเป็นจำนวนเงินจาก c ขึ้นไป
• ลูปจำนวนเงินจากมากไปน้อยทำให้แต่ละชนิดใช้ได้ไม่เกินหนึ่งเหรียญ ซึ่งเป็นอีกคำถามหนึ่ง
• ทุกแบบเป็น O(XK) เทียบกับ recursion ตรงๆ ที่เงินแค่ 40 บาทก็ใช้เวลาเป็นนาที