Bài toán đổi tiền


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type

Ngân hàng có \(n\) mệnh giá tiền có số lượng mỗi tờ tiền là vô hạn gồm \(a_1,a_2,...a_n\). Một người muốn đổi số tiền \(M\) theo các mệnh giá tiền này hãy tìm cách đổi sao cho số tờ tiền là ít nhất

Input

Dòng đầu chứa hai số \(n (1 \le n \le 100)\) là số loại mệnh giá ngân hàng có và số truy vấn \(q (1\le q \le 1000)\)

Dòng tiếp theo chứa n số nguyên dương không vượt quá \(10^4\) đôi một khác nhau là các loại mệnh giá tiền mà ngân hàng có

Cuối cùng gồm \(q\) dòng mỗi dòng một giá trị \(M (1 \le M \le 10^4)\) và số tiền muốn đổi

Ouput

Gồm \(q\) dòng mỗi dòng một số nguyên dương là số tờ tiền ít nhất đổi được, trong trường hộp không đổi được tiền thì xuất \(-1\)

Ví dụ 1

Input

3 2
1 7 5
10
18

Ouput

2
4

Giải thích : Đổi 10 gồm 2 tờ có mệnh giá 5 còn 18 thì có 4 tờ gồm \(5+5+7+1\)

Ví dụ 2

Input

3 2
15 6 8
11
12

Ouput

-1
2
tichpx

Comments


  • 1
    TICHPX  commented on May 28, 2021, 10:56 p.m.

    Thuật toán Best First Search cho bài toán đổi tiền

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n,q,MAX=1e4+1;
        cin>>n>>q;
        int a[n]; for(int &x:a) cin>>x; sort(a,a+n,greater<int>());
        map<int,int> M;
        priority_queue< pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > Q;
        Q.push({0,0}); 
        M[0]=0;
        while(Q.size())
        {
            int u=Q.top().second, v=Q.top().first; Q.pop();
            for(int x:a)
            if(x+u<MAX && M.find(x+u)==M.end())
            {
                M[x+u]=v+1;
                Q.push({v+1,x+u});
            }
        }
        while(q--)
        {
            int z;  cin>>z;
            if(M.find(z)==M.end()) M[z]=-1;
            cout<<M[z]<<"\n";
        }   
    
    }