通过动态规划算法使用c语言编译设有 n 种不同面值的硬币，各硬币的面值存于数组 T［1:n］中。现要用这些 面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组 Coins［1:n］中。 对任意钱数 0≤m≤20001，设计一个用最少硬币找钱 m 的方法。 输入： 输入的第一行中只有 1 个整数给出 n 的值,第 2 行起每行 2 个数，分别 是 T[j]和 Coins[j]。最后 1 行是要找的钱数 m。 输出： 程序运行结束时，将计算出的最少硬币数输出。问题无解时输出-1 除了输出最少硬币个数，还输出每种面额的硬币各用了多少个。

下面是通过动态规划算法使用 C 语言编写的代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define INF INT_MAX    // 表示无限大
#define MAXN 10005     // 最大钱数
#define MAXM 105       // 最大硬币种数

int T[MAXM];           // 硬币面值
int Coins[MAXM];       // 硬币个数
int dp[MAXN];          // dp 数组
int used[MAXM];        // 每种面额的硬币各用了多少个

int main()
{
    int n, m;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &T[i], &Coins[i]);
    }
    scanf("%d", &m);

    dp[0] = 0;
    for (int i = 1; i <= m; i++) {
        dp[i] = INF;
    }

    for (int i = 1; i <= n; i++) {
        for (int k = 0; k < T[i]; k++) {  // 枚举余数
            int cnt = 0;  // 记录当前面额硬币使用的个数
            for (int j = k; j <= m-T[i]; j += T[i]) {
                if (dp[j] < INF && Coins[i] > 0) {
                    if (dp[j+T[i]] > dp[j]+1) {
                        dp[j+T[i]] = dp[j] + 1;
                        used[i]++;
                        Coins[i]--;
                        cnt++;
                    }
                }
            }
            // 如果当前面额硬币使用的个数为 0，则后面的也都为 0
            if (cnt == 0) break;
        }
    }

    if (dp[m] == INF) {
        printf("-1\n");
    } else {
        printf("%d\n", dp[m]);
        printf("每种面额的硬币各用了多少个：\n");
        for (int i = 1; i <= n; i++) {
            printf("%d元硬币：%d个\n", T[i], used[i]);
        }
    }

    return 0;
}

需要特别注意的是，在枚举余数时，我们要从 0 开始枚举，这样就可以覆盖所有的余数。同时，为了减小时间复杂度，我们可以在枚举余数时，跳过那些余数不为 k 的钱数。例如，在枚举 T[i]=5 时，如果 k=1，那么我们只需要枚举钱数为 1, 6, 11, ... 的情况即可。