Hiểu bài toán

Bài toán yêu cầu tìm tổng số đồng xu tối thiểu cần trao đổi giữa hai bên (HD và HP) để HP nhận được đúng số tiền S đồng. HD sẽ đưa cho HP một số tiền X (với X >= S), và HP phải trả lại số tiền X - S. Vấn đề trở thành: tìm số tiền X >= S sao cho tổng số đồng xu dùng để tạo ra X và số đồng xu dùng để tạo ra X - S là nhỏ nhất. Chúng ta có thể coi đây là bài toán quy hoạch động để tìm số đồng xu ít nhất để tạo ra một số tiền.

Các cách tiếp cận

Cách Quy hoạch động cơ bản (DP)

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

int main(){
    int v,n;
    cin>>v>>n;
    vector<int> a;
    vector<int> dp(20001,INT_MAX-1);
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        a.push_back(x);
        dp[x]=1;
    }
    dp[0]=0;
    for(int i=2;i<=20000;i++){
        for(int j:a){
            if(i>j){
                dp[i]=min(dp[i],dp[i-j]+1);
            }
        }
    }
    int res = INT_MAX;
    for(int i=0;i+v<=20000;i++){
        res = min(res,dp[i]+dp[i+v]);
    }
    cout<<res;
}

• Time Complexity: O(MAX * N)
• Space Complexity: O(MAX)

Hàm dp[x] lưu số đồng xu ít nhất để tạo ra số tiền x. Ban đầu, gán dp[0] = 0 và dp[a[i]] = 1 cho các mệnh giá có sẵn. Duyệt qua tất cả các số tiền từ 1 đến MAX (20000), cập nhật dp[i] bằng cách thử các mệnh giá j, lấy dp[i-j] + 1 nếu nhỏ hơn. Sau khi có bảng DP, duyệt qua tất cả các số tiền X từ v (số tiền cần nhận) đến 20000 (một giới hạn an toàn), tính dp[X] + dp[X - v] và lấy giá trị nhỏ nhất. Ý tưởng là HD đưa X đồng, HP trả X - v đồng.

Cách Quy hoạch động tối ưu (DP Target)

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

const int INF = 1e9;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int S, n;
    cin >> S >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int MAX = S + 3000;
    vector<int> dp(MAX + 1, INF);
    dp[0] = 0;

    // DP: dp[x] = số xu ít nhất để tạo ra x đồng
    for (int coin : a)
        for (int i = coin; i <= MAX; i++)
            dp[i] = min(dp[i], dp[i - coin] + 1);

    int res = INF;
    for (int x = S; x <= MAX; x++) {
        if (dp[x] != INF && dp[x - S] != INF)
            res = min(res, dp[x] + dp[x - S]);
    }

    cout << res << '\n';
    return 0;
}

• Time Complexity: O(MAX * N)
• Space Complexity: O(MAX)

Phương pháp này giống phương pháp 1 nhưng được tối ưu hóa hơn một chút về mặt cấu trúc. Nó tính toán dp[x] cho x từ 0 đến MAX = S + 3000 (giới hạn trên hợp lý dựa trên mệnh giá lớn nhất). Vòng lặp DP duyệt qua từng mệnh giá, sau đó duyệt từ mệnh giá đó lên MAX. Cuối cùng, nó duyệt qua tất cả các giá trị x >= S để tìm min(dp[x] + dp[x - S]). Đây là cách tiếp cận chuẩn và hiệu quả nhất cho bài toán này.

Cách Quy hoạch động BFS (Tìm đích)

#include <bits/stdc++.h>
using namespace std;
long long m,n,t,p,k,l,r;
long long a[1000001];
long long d[1000001];
vector <long long> s;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(long long i = 1; i <= k; i++)
    {
        cin >> a[i];
    }
    for(long long i = 1; i <= n; i++)
    {
        d[i] = INT_MAX;
    }
    for(long long i = 1; i <= n; i++)
    {
        for(long long j = 1; j <= k; j++)
        {
            d[i] = min(d[i], d[abs(i - a[j])] + 1);
        }
    }
    for(long long i = 1; i <= n; i++)
    {
        for(long long j = 1; j <= k; j++)
        {
            d[i] = min(d[i], d[abs(i - a[j])] + 1);
        }
    }
    cout << d[n];
}

• Time Complexity: O(N * K)
• Space Complexity: O(N)

Code này có vẻ bị sai logic hoặc viết vội cho một bài toán khác (có thể là bài 'Change' nhưng cách tiếp cận khác). Nó tính d[i] dựa trên d[abs(i - a[j])]. Nếu ta coi đây là bài toán tìm đường đi ngắn nhất từ 0 đến n (với n là S), thì cách này chỉ tìm được số đồng xu để tạo ra chính xác S, không tính đến việc trả lại tiền thối. Tuy nhiên, trong ngữ cảnh bài toán này, nó không giải quyết đúng vấn đề 'HD đưa X, HP trả X-S'. Tuy nhiên, dựa trên tên biến n (thường là S) và k (số mệnh giá), nó có thể đang tìm cách tạo ra S bằng cách cộng trừ mệnh giá. Nếu chỉ xét trường hợp HP trả lại tiền (HD đưa đúng S) thì kết quả là d[S]. Nhưng bài toán yêu cầu tối thiểu tổng xu của cả 2 phía, nên cách này không đủ.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể quy về bài toán tìm số xu ít nhất để tạo ra một số tiền (Coin Change).
• Cần phải xem xét cả trường hợp HD đưa nhiều tiền hơn S và HP trả lại phần thừa.
• Giới hạn của số tiền cần xét (MAX) nên là S + max(coin) để đảm bảo tìm được lời giải tối ưu.

Lỗi thường gặp

• Quên xử lý trường hợp số tiền cần tạo ra lớn hơn rất nhiều so với S, dẫn đến sai lệch kết quả nếu đặt giới hạn DP quá nhỏ.
• Lầm tưởng bài toán chỉ là tìm cách tạo ra chính xác S (Coin Change) mà bỏ qua bước HP trả lại tiền thối.