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
    14

    4

    Với a = [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
    25

    4

    Với a = [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;
}