Hướng dẫn bài STUPATM - Máy rút tiền tự động (Khờ)

Mỗi một phương án trả tiền có dạng một vec-tơ , trong đó sao cho .

Chú ý: Bài toán này chỉ yêu cầu tìm một nghiệm bất kỳ.

Ta có thể cài đặt duyệt toàn bộ bằng quay lui hoặc xét dãy bit

Duyệt quay lui:

int x[nmax];//Vec-tơ nghiệm
void BT(int i, long long sum) {
    if (i > n) {
        if (sum == M) {
            inKQ();
            exit(0);    //Kết thúc chương trình, (không phải return)
        }
        return;
    }
    for (int j = 0; j <= 1; j++) {
        if (j * t[i] + sum <= M) {
            x[i] = j;
            BT(i + 1, sum + j * t[i]);
        }
    }
}