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

以下是使用 C 语言编写的最少硬币找钱的程序：

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

#define MAX_AMOUNT 20001

int t[MAX_AMOUNT], coins[MAX_AMOUNT], dp[MAX_AMOUNT];

int main() {
    int n, m;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d%d", &t[i], &coins[i]);
    }

    scanf("%d", &m);

    // 初始化 dp 数组
    for (int i = 1; i <= m; i++) {
        dp[i] = INT_MAX;
    }

    dp[0] = 0; // 凑出金额为 0 不需要硬币

    // 计算 dp 数组
    for (int i = 0; i < n; i++) {
        for (int j = m; j >= t[i]; j--) {
            for (int k = 0; k <= coins[i] && k * t[i] <= j; k++) {
                if (dp[j - k * t[i]] != INT_MAX) {
                    dp[j] = dp[j] < dp[j - k * t[i]] + k ? dp[j] : dp[j - k * t[i]] + k;
                }
            }
        }
    }

    if (dp[m] == INT_MAX) {
        printf("-1");
    } else {
        printf("%d\n", dp[m]);

        // 输出每种面额的硬币数量
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = m; j >= t[i]; j -= t[i]) {
                if (dp[j] == dp[j - t[i]] + 1) {
                    cnt++;
                }
            }
            printf("%d\n", cnt);
        }
    }

    return 0;
}

程序先读入硬币的面值和数量，然后计算最少硬币数和每种面额的硬币数量，最后输出结果。

程序使用三重循环计算 dp 数组，时间复杂度为 O(nm^2)。在钱数较大时可能会超时，可以使用滚动数组等方法进行优化。