[Dynamic] Part1.Bài toán cây ATM

Bài toán này nằm trong loạt bài giới thiệu thuật toán "Quy hoạch động" - Dynamic

Thuật toán quy hoạch động là gì ???? Trước khi bắt đầu chúng ta sẽ xem một ví dụ thực tế đơn giản để thấy thuật toán "Quy hoạch động" (Dynamic) hoạt động như thế nào và được ứng dụng làm gì!! 

1. ĐỀ BÀI

Để tiết kiệm tối đa chi phí vận hành và tăng tốc độ giao dich, các ngân hàng muốn thiết kế một thuật toán cho các cây ATM để cây ATM có thể trả được đúng số tiền dựa trên những loại tiền có trong ATM đó, và số tờ tiền rút ra là nhỏ nhất. Ví dụ : Một cây ATM chỉ còn tiền các mệnh giá 20$, 50$ , một khách hàng muốn rút 110$, thì cây ATM sẽ tính toán và trả 1 tờ 50$ và 3 tờ 20$. Nếu khách hàng muốn rút 60$ thì cây ATM sẽ báo không thực hiện được giao dịch. Hãy viết thuật toán thực hiện yêu cầu trên, đầu ra ghi số lượng tờ tiền rút ra, nếu không thể thực hiện giao dịch, in ra -1.


Giới hạn : Số Testcase NT không quá 30, Số loại tiền N không quá 10, Giá trị 1 loại tiền không quá 10000, Số tiền rút ra không quá 1000000.

INPUT : 

2 //- Dòng đầu tiên NT chỉ số lượng testcase
1 //- Testcase thứ 1
2 //- Dòng đầu tiên mỗi testcase chứa số loại tiền ( 2 loại ) N
20 //- Mệnh giá 20$
50 //- Mệnh giá 50$
110 //- Hết N dòng , dòng này cho biết lượng tiền khách hàng muốn rút 110$
2 //- Testcase thứ 2
2
20
50
60

OUTPUT :
Case #1 4   // Số tờ tiền 4 gồm 1 tờ 50$ và 3 tờ 20$
Case #2 -1  //  Không thực hiện được giao dịch

Download File Testcase

Code mẫu:

#include <stdio.h>

#define INF 1000001
int Value[10];
long Withdraw;
long F[11][1000001];

long min(long a,long b){
    return ((a<b) ? a : b);
}
int main(void)
{
    freopen("input.txt", "r", stdin);
    int test_case, NT;
    scanf("%d", &NT);
    for(test_case = 1; test_case <= NT; test_case++)
    {
        int i, N;
        long j;
        int Case_Number;
        scanf("%d",&Case_Number);
        scanf("%d",&N);
        for (i = 1; i <= N; i++)scanf("%d", &Value[i]);
        scanf("%ld", &Withdraw);

        for(j = 1;j <= Withdraw; j++)
            F[1][j] = j%Value[1] ? INF : j/Value[1];

        for(i = 2 ;i <= N; i++){
            for(j=1;j<=Withdraw;j++){
                if(j<Value[i]) F[i][j]=F[i-1][j];
                    else F[i][j]=min(F[i-1][j],F[i][j-Value[i]]+1);
            }
        }       
        if(F[N][Withdraw]>=INF)printf("Case #%d Impossible\n",test_case);
        else printf("Case #%d %ld\n",test_case, F[N][Withdraw]);
    }
    return 0;
}