设一硬币系统有n种面值，第i种硬币的面值和重量分别为p i ​ 和w i ​ ，硬币面值的单位为元，且有p 1 ​ <p 2 ​ <⋯<p n ​ 和p 1 ​ =1，现需要给别人找Y∈Z + 元钱，试确定一找零钱方案，使得所找的硬币的总重量最轻。 要求使用如下动态规划思想 设F k ​ (y)表示使用前k种硬币去找y元钱时所找硬币的最轻总重量，则F k ​ (y)的递推方程定义如下： F k ​ (y)= ⎩ ⎨ ⎧ ​ 0≤x k ​ ≤⌊ p k ​ y ​ ⌋ min ​ {x k ​ ⋅w k ​ +F k−1 ​ (y−x k ​ ⋅p k ​ )}, y⋅w 1 ​ , ​ k>1 k=1 ​ 设x k ​ (y)表示F k ​ (y)取得最小值时第k种硬币所找的硬币数x k ​ ，为了能够方便构造最优解，需要每算出一个F k ​ (y)时，记录一下对应的x k ​ (y)。 c语言实现

以下是一个用C语言实现的动态规划算法，用于解决找零钱问题：

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

#define MAX_COINS 100
#define MAX_AMOUNT 10000
#define INF 0x3f3f3f3f

int p[MAX_COINS];
int w[MAX_COINS];
int x[MAX_COINS];
int f[MAX_AMOUNT];

void dp(int n, int m) {
    for (int i = 1; i <= m; i++) {
        f[i] = INF;
        for (int j = 1; j <= n; j++) {
            if (i >= p[j]) {
                int tmp = f[i - p[j]] + w[j];
                if (tmp < f[i]) {
                    f[i] = tmp;
                    x[j] = i - p[j];
                }
            }
        }
    }
}

int main() {
    int n, m;
    printf("请输入硬币种类数n和要找的钱数m：");
    scanf("%d%d", &n, &m);
    printf("请输入%d种硬币的面值p和重量w：\n", n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i], &w[i]);
    }

    dp(n, m);

    printf("找零钱方案如下：\n");
    int j = n;
    while (m > 0) {
        if (x[j] <= m && m < x[j] + p[j]) {
            printf("用面值为%d的硬币%d枚\n", p[j], (m - x[j]) / p[j]);
            m = x[j];
        } else {
            j--;
        }
    }
    printf("所找硬币的最轻总重量为%d\n", f[m]);

    return 0;
}

这个算法首先读入硬币的种类数n和要找的钱数m，以及每种硬币的面值p和重量w。然后使用动态规划算法计算出找零钱方案，并记录每种硬币所找的硬币数x。最后，根据x数组输出最优解。