找零钱问题c语言

好的，以下是找零钱问题的C语言代码实现：

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

#define MAX_N 1000
#define MAX_Y 10000

int n, Y;
int p[MAX_N+1], w[MAX_N+1];
int dp[MAX_N+1][MAX_Y+1], x[MAX_N+1][MAX_Y+1];

int main() {
    // 读入数据
    scanf("%d %d", &n, &Y);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &p[i], &w[i]);
    }

    // 初始化dp数组
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= Y; j++) {
            dp[i][j] = MAX_Y * MAX_N; // 初始化为一个较大的值
        }
    }
    dp[0][0] = 0;

    // 动态规划求解
    for (int k = 1; k <= n; k++) {
        for (int y = 0; y <= Y; y++) {
            for (int xk = 0; xk <= y/p[k]; xk++) {
                int t = dp[k-1][y - xk * p[k]] + xk * w[k];
                if (t < dp[k][y]) {
                    dp[k][y] = t;
                    x[k][y] = xk;
                }
            }
        }
    }

    // 输出结果
    printf("最轻总重量为：%d\n", dp[n][Y]);
    printf("最优解为：\n");
    for (int k = n; k >= 1; k--) {
        int xk = x[k][Y];
        printf("第%d种硬币找%d个\n", k, xk);
        Y -= xk * p[k];
    }

    return 0;
}

注意，这里我们初始化dp数组时需要将所有元素初始化为一个较大的值，这样在计算dp[k][y]时才能正确地取min。在本代码中，我们将所有元素初始化为MAX_Y * MAX_N，其中MAX_Y和MAX_N分别表示Y和n的最大值。同时，在计算dp数组时，我们需要注意数组下标的范围，需要从0开始到n和Y的值。