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

好的，我的思路是使用动态规划来解决这个问题。
具体来说，我们设 dp[i] 表示要找 i 元钱所需要的最少硬币数。那么对于每一个 dp[i]，我们可以枚举使用哪一种面值的硬币来凑出 i，即：
dp[i] = min(dp[i - T[j]] + 1)，其中 T[j] <= i 且 Coins[j] > 0。
其中，dp[i - T[j]] 表示已经凑出 i - T[j] 元钱，再加上面值为 T[j] 的硬币即可凑出 i 元钱。
需要注意的是，由于硬币数量有限，我们需要在枚举时判断 Coins[j] 是否还有剩余。
最终答案即为 dp[m]。如果 dp[m] 为正无穷，说明无解，输出 -1 即可。

以下是 C++ 代码实现：

相关问题

设有n 种不同面值的硬币，各硬币的面值存于数组T［1:n］中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins［1:n］中。 对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。

这个问题可以用动态规划来解决。设f(i)表示找i元钱所需的最少硬币数量，则有状态转移方程：

f(i) = min{f(i-T[j])+1}，其中T[j]表示第j种硬币的面值，且T[j]<=i且Coins[j]>0。

初始状态：f(0)=0，即找0元钱不需要任何硬币。

最终答案为f(m)。

下面是C++代码实现：

const int INF = 0x3f3f3f3f; // 定义无穷大
int f[20005]; // f[i]表示找i元钱所需的最少硬币数量
int T[105], Coins[105]; // T数组存储硬币面值，Coins数组存储硬币个数

int solve(int m, int n) {
    memset(f, INF, sizeof(f)); // 初始化为无穷大
    f[0] = 0; // 找0元钱不需要任何硬币
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (T[j] <= i && Coins[j] > 0) {
                f[i] = min(f[i], f[i-T[j]]+1);
                Coins[j]--; // 使用了第j种硬币
            }
        }
        for (int j = 1; j <= n; j++) {
            if (T[j] <= i) {
                Coins[j]++; // 恢复第j种硬币的个数
            }
        }
    }
    if (f[m] == INF) return -1; // 无解的情况
    else return f[m];
}

其中m表示需要找的钱数，n表示硬币的种类数。函数返回值为最少硬币数量，若无解则返回-1。

设有 n 种不同面值的硬币，各硬币的面值存于数组 T［1:n］中。现要用这些 面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组 Coins［1:n］中。 对任意钱数 0≤m≤20001，设计一个用最少硬币找钱 m 的方法。

这是一个典型的动态规划问题，可以使用动态规划算法来解决。

定义状态 dp[i] 表示找钱金额为 i 时所需的最少硬币数。则对于每个 i，都可以枚举使用哪种面值的硬币 Coin[j]，来更新状态 dp[i]。

具体来说，对于每个 i，遍历数组 Coins，如果当前硬币面值为 Coin[j]，并且 i-Coin[j] 可以被找零（即 dp[i-Coin[j]] 不为无穷大），则可以更新状态 dp[i]：

dp[i] = min(dp[i], dp[i-Coin[j]] + 1)

其中，dp[i-Coin[j]] + 1 表示使用当前硬币 Coin[j]，再加上找钱金额为 i-Coin[j] 时所需的最少硬币数。

最终，dp[m] 就是所需的最少硬币数。

下面是 C++ 代码实现：

const int INF = 0x3f3f3f3f;
const int MAXN = 20010;

int T[MAXN], Coins[MAXN], dp[MAXN];

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

    memset(dp, INF, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; 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]] != INF) {
                    dp[j] = min(dp[j], dp[j - k * T[i]] + k);
                }
            }
        }
    }

    printf("%d\n", dp[m] == INF ? -1 : dp[m]);
    return 0;
}

其中，第一个循环枚举硬币面值，第二个循环枚举钱数，第三个循环枚举使用当前硬币的个数。在第三个循环中，需要判断 dp[j-k\*T[i]] 是否为 INF，如果是，则说明无法使用当前硬币找零 j-k\*T[i]，需要跳过。