หาจำนวนคำตอบของสมการเชิงเส้น n ตัวแปรด้วย C++

ภาพรวมปัญหา

ได้รับสมการเชิงเส้น n ตัวแปร: coeff1·x1 + coeff2·x2 + ... + coeffn·xn = value

หาจำนวนคำตอบที่เป็นจำนวนเต็มบวกหรือศูนย์ (non-negative integer solutions)

ตัวอย่าง

อินพุต

coeff[] = {3, 1}, value = 4

เอาต์พุต

1

คำอธิบาย

สมการ: 3x + y = 4
คำตอบ: x = 0, y = 4

วิธีแก้ปัญหา

ใช้ Recursion (Backtracking) ลองทุกค่าที่เป็นไปได้ของตัวแปร

โค้ดตัวอย่าง

#include <iostream>
using namespace std;

int countSolutionsEq(int coeff[], int start, int end, int value) {
    if (value == 0)
        return 1;
    
    int coefCount = 0;
    for (int i = start; i <= end; i++)
        if (coeff[i] <= value)
            coefCount += countSolutionsEq(coeff, i, end, value - coeff[i]);
    
    return coefCount;
}

int main() {
    int coeff[] = {3, 5, 1, 2};
    int value = 6;
    int n = sizeof(coeff) / sizeof(coeff[0]);
    cout << "The number of solutions of the linear equation is " 
         << countSolutionsEq(coeff, 0, n - 1, value);
    return 0;
}

เอาต์พุต

The number of solutions of the linear equation is 8

สรุป

เป็นปัญหา Coin Change / Integer Partition แบบอนุญาตให้ใช้ตัวแปรซ้ำได้ ใช้ Recursion แบบ Unbounded Knapsack

หมายเหตุ: สำหรับค่าใหญ่ควรใช้ Dynamic Programming (DP) แทน Recursion เพื่อหลีกเลี่ยงการคำนวณซ้ำ