นับจำนวนในช่วง [1,N] ที่สร้างได้จาก X และ Y ใน C++

ภาพรวมปัญหา

ให้จำนวน X, Y และ N (ช่วง [1,N]) ต้องการนับจำนวนในช่วงที่สามารถสร้างได้จาก X และ Y เท่านั้น หลายครั้งก็ได้ เช่น X=2, Y=3 → 6 = 2+2+2 หรือ 3+3, 7 = 2+2+3

ตัวอย่าง

Input: N=10, X=4, Y=3

Output: 7

คำอธิบาย: 3, 4, 6(3+3), 7(3+4), 8(4+4), 9(3+3+3), 10(3+3+4)

Input: N=10, X=5, Y=4

Output: 5

คำอธิบาย: 4, 5, 8(4+4), 9(4+5), 10(5+5)

แนวทางแก้ปัญหา (Dynamic Programming / Coin Change)

นี่คือปัญหา Coin Change / Unbounded Knapsack แบบนับจำนวนจำนวนที่สร้างได้

1. สร้าง boolean array dp[N+1] โดย dp[i] = true ถ้าสร้าง i ได้
2. dp[0] = true
3. สำหรับแต่ละเหรียญ (X และ Y) อัปเดต dp
4. นับจำนวน i ที่ dp[i] == true

โค้ดตัวอย่าง (DP - แนะนำ)

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

int constructNums_dp(int n, int x, int y) {
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    
    int coins[] = {x, y};
    for (int coin : coins) {
        for (int i = coin; i <= n; i++) {
            if (dp[i - coin]) dp[i] = true;
        }
    }
    
    int count = 0;
    for (int i = 1; i <= n; i++) if (dp[i]) count++;
    return count;
}

int main() {
    int N = 20, X = 5, Y = 4;
    cout << "Total numbers: " << constructNums_dp(N, X, Y);
    return 0;
}

โค้ดต้นฉบับ (Greedy-ish - อาจผิดบางกรณี)

// วิธีต้นฉบับ: ลบ X และ Y ซ้ำๆ - อาจไม่ครอบคลุมทุกกรณี
int constructNums_original(int n, int x, int y) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        int num = i;
        while (num > 0) {
            while (num % x == 0 && num != 0) num -= x;
            while (num % y == 0 && num != 0) num -= y;
            if (num > x && num > y) num -= x + y;
            else break;
        }
        if (num == 0) count++;
    }
    return count;
}

ผลลัพธ์

Total numbers constructed using X & Y only: 14

ความซับซ้อน

ข้อสังเกตทางคณิตศาสตร์ (Frobenius Coin Problem)

ถ้า gcd(X,Y) = 1 จำนวนที่สร้างไม่ได้ สูงสุดคือ XY - X - Y (Frobenius number)

จำนวนที่สร้างไม่ได้ทั้งหมด = (X-1)(Y-1)/2