CTDL và giải thuật - Giải thuật Qui hoạch động
Một ngân hàng có rất nhiều tiền với nhiều mệnh giá khác nhau, số lượng tờ tiền mỗi mệnh giá được coi là vô hạn.
Cho mảng a
chứa các phần tử là [a0, a1, a2..]
. Là các mệnh giá mà ngân hàng đó có.
Một người đến rút số tiền là x
đồng ở ngân hàng, người đó muốn nhận về số tiền đó với số tờ tiên là ít nhất. Hãy tính số tờ tiền ít nhất mà ngân hàng phải để sao cho tổng giá trị của chúng là n
đồng. Nếu không có cách nào đổi được thì trả về 0
.
Ví dụ:
- Test mẫu 1:
Input Output 3
1 2 5
144
Vớia = [1, 2, 5]
,x = 14
, thì kết quả mong muốn là4
:
Vì ngân hàng sẽ trả về người đó:2
tờ mệnh giá5
đồng.2
tờ mệnh giá2
đồng.
Có nhiều cách để trả tiền, nhưng cách trên thì số lượng tờ tiền mà người đó cầm là ít nhất.
- Test mẫu 2:
Input Output 4
1 2 8 10
254
Vớia = [1, 2, 8, 10]
,x = 25
, thì kết quả mong muốn là4
:
Vì ngân hàng sẽ trả về người đó:3
tờ mệnh giá8
đồng.1
tờ mệnh giá1
đồng.
Có nhiều cách để trả tiền, nhưng cách trên thì số lượng tờ tiền mà người đó cầm là ít nhất.
Hướng dẫn bài tập.
Ý tưởng:
Sử dụng giải thuật quy hoạch động.
Tạo một dãy l[i..x]
, với l[k]
số tiền ít nhất của cách đổi số tiền là k
.
Với số tiền cần đổi là k
, nếu chọn tờ tiền a[j]
thì lúc đó l[k] = l[k - a[j]]
.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
using namespace std;
int a[100001];
int l[100001];
int moneyChange(int a[], int n, int x)
{
for (int i = 0; i <= x; i++)
l[i] = 0;
for (int i = 0; i < n; i++)
l[a[i]] = 1;
for (int i = 1; i <= x; i++)
for (int j = 0; j < n; j++)
if (i >= a[j]){
if ((l[i] > l[i-a[j]] + 1 && l[i-a[j]] != 0) || (l[i] == 0 && l[i-a[j]] != 0)){
l[i] = l[i-a[j]] + 1;
}
}
return l[x];
}
int main(){
int n, x;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
cin >> x;
cout << moneyChange(a, n, x);
return 0;
}