Rút Tiền ATM

Nguồn: Đề luyện thi HSG Tin học Độ khó: Trung bình Vét cạn Hàng đợi Duyệt tập con Quay lui

Đề bài

Bài 2: Rút tiền ATM

Một máy ATM hiện có $n$ $(n \le 20)$ tờ tiền có giá trị $t_1, t_2, \ldots, t_n$. Hãy đưa ra một cách trả với số tiền đúng bằng $S$.

Input

• Dòng 1: 2 số $n$ và $S$.
• Dòng 2: gồm $n$ số $t_1, t_2, \ldots, t_n$.

Output: Nếu có thể trả đúng thì đưa ra cách trả, nếu không ghi $-1$.

Ví dụ – input

10 390
200 10 20 20 50 50 50 50 100 100

Ví dụ – output

20 20 50 50 50 100 100

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Trước khi vào bài, các bạn nhớ giúp mình ngưỡng quen thuộc: với giới hạn 1 giây thì toàn bài chỉ nên lặp khoảng $(3 \div 5) \cdot 10^7$ lần (C/C++) là an toàn, $10^8$ thì hên xui. Đề này tuy không ghi rõ nhưng có vẻ được lấy từ một kỳ thi học sinh giỏi cấp trường/tỉnh, mà các kỳ thi này thường quy định chung 1 giây cho mọi bài, nên các bạn cứ canh theo ngưỡng đó.

Giải thích ví dụ: máy có 10 tờ tiền $200, 10, 20, 20, 50, 50, 50, 50, 100, 100$ và cần trả đúng $S = 390$. Đáp án mẫu chọn 7 tờ $20 + 20 + 50 + 50 + 50 + 100 + 100 = 390$. Nhưng đề chỉ yêu cầu đưa ra một cách trả, nên cách khác như $200 + 20 + 20 + 50 + 100 = 390$ cũng đúng. Code trong bài sẽ in ra cách này – khác output mẫu nhưng vẫn hợp lệ nhé. Nếu không có cách chọn nào ra đúng $S$ thì in $-1$.

Đúng dạng gì?

Bài này đọc đề vào là thấy ngay dạng của nó: "Tìm dãy con có tổng bằng S". Cách tối ưu nhất là quy hoạch động – bài toán rất rất căn bản của QHĐ, tựa như kiểm tra số nguyên tố vậy đó, các bạn gõ từ khoá đó lên Google là ra rất nhiều bài viết. Quan trọng là nhìn ra đúng dạng của nó.

Tuy nhiên bài này mình sẽ không hướng dẫn cách quy hoạch động, vì nó đã quá phổ biến rồi. Thay vào đó mình hướng dẫn cách tệ nhất: vét cạn (hay còn gọi là duyệt trâu 😁). Tại sao? Theo quan điểm của mình, nếu cách làm tệ nhất mà còn chưa làm được thì đừng vội tìm hiểu cách tốt hơn, vì sẽ chưa đủ "nội công" để hiểu đâu. Hiểu được cách vét cạn rồi thì các bạn sẽ thấy được chỗ chưa tốt của nó, từ đó tối ưu dần lên và lĩnh ngộ những cách tốt hơn. Thêm nữa, lúc nào mình cũng khuyến khích: ngoài cách tối ưu, hãy viết thêm một bản vét cạn để làm công cụ kiểm tra tính CHÍNH XÁC của cách tối ưu – vì vét cạn (cài đặt đúng) thì không thể sai được.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn tập con bằng hàng đợi (không đệ quy)Cách 2Vét cạn bằng đệ quy quay lui (chọn / không chọn)

Cách 1Vét cạn tất cả tập con bằng hàng đợi – O(2^n · n)

Vét cạn cho bài này nghĩa là ta đi xét hết tất cả các tập con của danh sách tờ tiền. Xét đến khi nào gặp tập con có tổng bằng $S$ thì dừng lại in ra; xét đến tận cùng vẫn không có thì in $-1$. Đơn giản là vậy thôi.

Ví dụ danh sách có 5 phần tử đánh số từ 1 đến 5 thì các tập con (theo số thứ tự) không trùng nhau là:

Số phần tử	Các tập con
1	1 · 2 · 3 · 4 · 5
2	12 · 13 · 14 · 15 · 23 · 24 · 25 · 34 · 35 · 45
3	123 · 124 · 125 · 134 · 135 · 145 · 234 · 235 · 245 · 345
4	1234 · 1235 · 1245 · 1345 · 2345
5	12345

Với mỗi tập con, ta cộng các tờ tiền ở các vị trí tương ứng. Như ví dụ của đề, khi xét đến tập con 5 phần tử $\{1, 3, 4, 5, 9\}$, tức các tờ $200, 20, 20, 50, 100$, ta thấy tổng bằng 390 nên dừng luôn và in ra. Ta xét từ tập con ít phần tử nhất trở lên, trong mỗi tập thì vị trí tăng dần; gặp tập đầu tiên thỏa mãn là dừng, tội gì mất công xét tiếp 😄.

Để sinh ra mọi tập con, người ta thường dùng đệ quy quay lui (Backtracking) – cài đặt ngắn gọn (xem Cách 2), nhưng tư tưởng không dễ hiểu với bạn mới bắt đầu. Nên ở đây mình hướng dẫn cách sinh tập con không dùng đệ quy, nhìn thấy rõ quy trình hơn:

Sinh tập con bằng hàng đợi

1. Hàng đợi (Queue) chứa các tập con, mỗi phần tử là một mảng 1 chiều. Ban đầu cho vào hàng đợi các tập 1 phần tử: $\{1\}, \{2\}, \ldots, \{n\}$.
2. Lấy lần lượt từng mảng ra khỏi hàng đợi – đó chính là tập con cần xét. Gọi $x$ là phần tử cuối của mảng.
3. Nếu $x \lt n$ thì thêm vào hàng đợi $n - x$ mảng mới: giữ nguyên mảng vừa lấy ra, gắn thêm vào cuối một phần tử lần lượt là $x + 1, x + 2, \ldots, n$.
4. Lặp lại đến khi hàng đợi rỗng.

Mô phỏng với $n = 5$: ban đầu hàng đợi là $\{1\}, \{2\}, \{3\}, \{4\}, \{5\}$.

• Lấy ra $\{1\}$: phần tử cuối là 1 < 5 nên thêm $\{1,2\}, \{1,3\}, \{1,4\}, \{1,5\}$.
• Lấy ra $\{2\}$: thêm $\{2,3\}, \{2,4\}, \{2,5\}$. Lấy ra $\{3\}$: thêm $\{3,4\}, \{3,5\}$. Lấy ra $\{4\}$: thêm $\{4,5\}$.
• Lấy ra $\{5\}$: phần tử cuối là 5, không thỏa $\lt n$ nên không thêm được gì.
• Lấy ra $\{1,2\}$: thêm $\{1,2,3\}, \{1,2,4\}, \{1,2,5\}$. Lấy ra $\{1,3\}$: thêm $\{1,3,4\}, \{1,3,5\}$. ... và cứ thế.
• Cuối cùng lấy ra $\{1,2,3,4,5\}$, không thêm được gì, hàng đợi rỗng ⇒ dừng.

Toàn bộ những lần lấy ra ở trên chính là toàn bộ các tập con, đúng thứ tự như bảng phía trên: số phần tử tăng dần từ 1 đến $n$, trong từng nhóm thì vị trí tăng dần. Các bạn tự nhập dữ liệu vào khung dưới đây rồi bấm Tiếp để xem từng lần lấy ra / thêm vào nhé (ô cam: các tờ tiền của tập đang xét; chip xanh: các mảng vừa được thêm vào hàng đợi):

n và S Các tờ tiền

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    queue<vector<int>> q;
    int n;
    long long s;
    cin >> n >> s;
    long long a[n + 1];
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        vector<int> b;
        b.push_back(i);
        q.push(b);
    }
    while(!q.empty()){
        vector<int> temp = q.front();
        q.pop();
        long long sum = 0;
        for(int i = 0; i < (int)temp.size(); ++i){
            sum += a[temp[i]];
        }
        if(sum == s){
            for(int i = 0; i < (int)temp.size(); ++i){
                cout << a[temp[i]] << " ";
            }
            return 0;
        }
        int x = temp[(int)temp.size() - 1];
        while(x < n){
            temp.push_back(++x);
            q.push(temp);
            temp.pop_back();
        }
    }
    cout << -1;
    return 0;
}

import sys
from collections import deque

data = sys.stdin.read().split()
n, s = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
q = deque()
for i in range(1, n + 1):
    q.append([i])
found = False
while q:
    temp = q.popleft()
    total = 0
    for p in temp:
        total += a[p]
    if total == s:
        print(*[a[p] for p in temp])
        found = True
        break
    x = temp[-1]
    while x < n:
        x += 1
        q.append(temp + [x])
if not found:
    print(-1)

Một số giải thích cho code ở trên:

1. Vòng lặp for đầu tiên trong hàm main để đọc mảng từ input, đồng thời mình tận dụng nó để đưa luôn vào hàng đợi $n$ mảng 1 chiều $\{1\}, \{2\}, \ldots, \{n\}$.
2. Mình dùng queue có sẵn trong STL C++ cho nhanh gọn (đi thi thực tế cũng không ai tự cài đặt lại, tự cài lỡ xui sai thì toang 😅), và mảng 1 chiều thì dùng vector – mảng động với nhiều hàm hỗ trợ sẵn rất tiện.
3. Mỗi temp lấy ra chứa các vị trí của tập con, ví dụ temp = {1, 2, 3} nghĩa là đang xét các tờ ở vị trí 1, 2, 3 (tính từ 1, nên mảng a khai báo $n + 1$ phần tử và bỏ qua index 0). Tờ tiền tương ứng là a[temp[i]], cộng hết vào sum, nếu bằng s thì in các a[temp[i]] ra.
4. Bước sinh mảng mới: x là phần tử cuối của temp; trong khi x < n thì temp.push_back(++x) (tăng x trước rồi mới đưa vào cuối mảng), đẩy temp vào hàng đợi, rồi temp.pop_back() bỏ phần tử vừa thêm để lặp tiếp với x kế tiếp.

Về kiểu dữ liệu

Đề không ghi giới hạn của $S$ và $t_i$, nên trong code trên mình để s, a[], sum là long long cho chắc ăn (bản gốc của mình dùng int) – tổng 20 tờ tiền lớn vẫn không lo tràn số.

Khung chạy tay (để dễ theo dõi, giới hạn $n \le 6$):

C++▶ Chạy tay từng dòng codeCách 1: lấy từng tập con ra khỏi hàng đợi, tính tổng, nếu chưa bằng S thì sinh các tập con dài hơn.

Dữ liệu vào (stdin) – sửa thoải mái4 70 50 10 20 40

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 queue<vector<int>> q;

6 int n;

7 long long s;

8 cin >> n >> s;

9 long long a[n + 1];

10 for(int i = 1; i <= n; ++i){

11 cin >> a[i];

12 vector<int> b;

13 b.push_back(i);

14 q.push(b);

15 }

16 while(!q.empty()){

17 vector<int> temp = q.front();

18 q.pop();

19 long long sum = 0;

20 for(int i = 0; i < (int)temp.size(); ++i){

21 sum += a[temp[i]];

22 }

23 if(sum == s){

24 for(int i = 0; i < (int)temp.size(); ++i){

25 cout << a[temp[i]] << " ";

26 }

27 return 0;

28 }

29 int x = temp[(int)temp.size() - 1];

30 while(x < n){

31 temp.push_back(++x);

32 q.push(temp);

33 temp.pop_back();

34 }

35 }

36 cout << -1;

37 return 0;

38}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Thời gian: trường hợp xấu nhất (không có cách trả) phải xét toàn bộ $2^n - 1$ tập con. Với $n = 20$ là $1\,048\,575$ – cứ coi như hơn $10^6$ tập, mỗi tập tối đa 20 phần tử ⇒ khoảng $20 \cdot 10^6 = 2 \cdot 10^7$ phép cộng, vẫn thỏa ngưỡng 1 giây, không sợ TLE. Phần đọc $n$ tờ tiền thì chẳng đáng bao nhiêu.
• Không gian: hàng đợi lúc đông nhất chứa khoảng hai "lớp" tập con liền nhau, cỡ $\binom{20}{10} + \binom{20}{11} \approx 3.5 \cdot 10^5$ mảng, mỗi mảng tối đa 20 số – vẫn nằm trong vài chục MB.

Không gian$O\left(\binom{n}{n/2} \cdot n\right)$

Thời gian$O(2^n \cdot n)$

Chỉ ổn vì n ≤ 20

May mắn đề cho $n$ tối đa chỉ 20 nên vét cạn vẫn ổn. Nếu $n$ lớn hơn nữa (ví dụ 30, 40) thì $2^n$ tăng vọt và cách này sẽ TLE ngay – lúc đó phải dùng cách tối ưu hơn như quy hoạch động "tìm dãy con có tổng bằng S". Nhưng vẫn hãy cài đặt bản vét cạn này để kiểm tra tính chính xác các bạn nhé, nó hay lắm đấy ^^. Với Python thì cách hàng đợi khá chậm vì phải tạo hơn 1 triệu list (khoảng 3 giây khi $n = 20$), bạn nào code Python nên dùng Cách 2.

Cách 2Vét cạn bằng đệ quy quay lui – O(2^n)

Như mình đã nói ở trên, đây là cách thường dùng để duyệt tập con và cài đặt rất ngắn gọn (từ khoá: "Liệt kê các tập con của dãy N phần tử bằng đệ quy quay lui"). Hiểu được cách hàng đợi rồi thì xem đoạn code đệ quy cũng sẽ dễ hiểu thôi.

Ý tưởng: lần lượt quyết định cho từng tờ tiền $i = 1, 2, \ldots, n$: chọn tờ đó (thêm vào danh sách chon, cộng vào tổng) hoặc không chọn. Hàm thu(i, sum) trả về true nếu từ trạng thái hiện tại có thể đi tiếp ra một cách trả đúng $S$:

• Nếu tổng hiện tại đã bằng $S$ (và đã chọn ít nhất 1 tờ) ⇒ tìm được rồi, trả về true ngay – danh sách chon chính là đáp án.
• Nếu đã quyết định hết $n$ tờ ($i \gt n$) mà chưa đủ ⇒ nhánh này thất bại.
• Thử chọn tờ $i$: chon.push_back(i) rồi gọi thu(i + 1, sum + a[i]); nếu thất bại thì quay lui: chon.pop_back() và thử nhánh không chọn thu(i + 1, sum).

Cách này mỗi tập con chỉ "đi qua" một lần và tổng được cộng dần theo đường đi, không phải cộng lại từ đầu như Cách 1, nên nhanh hơn hẳn. Đáp án tìm được có thể khác Cách 1 (với ví dụ của đề code in ra $200\ 20\ 20\ 50\ 50\ 50$), nhưng đề chấp nhận cách trả bất kỳ nên vẫn đúng.

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int n;
long long s, a[25];
vector<int> chon;

bool thu(int i, long long sum){
    if(sum == s && !chon.empty()) return true;
    if(i > n) return false;
    chon.push_back(i);
    if(thu(i + 1, sum + a[i])) return true;
    chon.pop_back();
    return thu(i + 1, sum);
}

int main(){
    cin >> n >> s;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    if(thu(1, 0)){
        for(int i = 0; i < (int)chon.size(); ++i){
            cout << a[chon[i]] << " ";
        }
    }
    else cout << -1;
    return 0;
}

import sys
sys.setrecursionlimit(10000)

data = sys.stdin.read().split()
n, s = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
chon = []

def thu(i, total):
    if total == s and chon:
        return True
    if i > n:
        return False
    chon.append(i)
    if thu(i + 1, total + a[i]):
        return True
    chon.pop()
    return thu(i + 1, total)

if thu(1, 0):
    print(*[a[p] for p in chon])
else:
    print(-1)

Đánh giá độ phức tạp của cách làm này:

• Thời gian: cây đệ quy có tối đa $2^{n+1}$ lời gọi, mỗi lời gọi $O(1)$ ⇒ $O(2^n)$; với $n = 20$ chỉ khoảng 2 triệu lời gọi, C++ chạy chừng 0.02 giây.
• Không gian: độ sâu đệ quy và mảng chon tối đa $n$ ⇒ $O(n)$.

Không gian$O(n)$

Thời gian$O(2^n)$

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 400 bộ test ngẫu nhiên ($n \le 9$), đối chiếu với kết quả duyệt bitmask: khi có cách trả thì các tờ in ra đều lấy đúng từ máy và có tổng đúng bằng $S$, khi không có thì in $-1$ – khớp hết. Với $n = 20$ và không có cách trả (trường hợp xấu nhất), Cách 1 C++ chạy khoảng 0.37 giây (Python khoảng 3.2 giây), Cách 2 C++ khoảng 0.02 giây (Python khoảng 0.45 giây).

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇