可以用二维数组记录数量么
时间: 2023-12-13 21:03:51 浏览: 67
当然可以,只需要将 `count` 数组改为二维数组即可。修改后的代码如下:
```
#include <string.h>
#include <stdio.h>
#define MAX 20002
#define INF 9999999
#define min(a,b) (a)>(b)?(b):(a)
int T[11], Coins[11], n; //硬币面值数组 T[],可以使用的各种面值的硬币个数数组 Coins[], n 种不同面值的硬币
int c[MAX]; //数组 c[]存放要找的最少硬币个数
int m; //要找的钱数 m
void init() {
int i;
printf("输入硬币的面值种数:");
scanf("%d", &n);
printf("\n 输入硬币面值及其此面值硬币的个数:\n");
for (i = 0; i < n; ++i)
scanf("%d %d", &T[i], &Coins[i]);
printf("\n 输入要找的钱数:");
scanf("%d", &m);
}
int main() {
int i, j, k;
int count[11][MAX]; //记录每种面额的硬币各用了多少个
init();
for (i = 0; i <= m; ++i)
c[i] = INF;
c[0] = 0;
for (i = 0; i < n; ++i) {
for (j = 1; j <= Coins[i]; ++j) {
for (k = m; k >= T[i]; --k) {
if (c[k] > c[k - T[i]] + 1) {
c[k] = c[k - T[i]] + 1;
memset(count[i], 0, sizeof(count[i]));
count[i][k] = j;
} else if (c[k] == c[k - T[i]] + 1) {
count[i][k] = j;
}
}
}
}
if (c[m] != INF) {
printf("\n 最少硬币个数为:%d\n", c[m]);
printf("各种面额的硬币使用个数分别为:\n");
for (i = 0; i < n; ++i) {
printf("%d元硬币使用个数分别为:\n", T[i]);
for (k = T[i]; k <= m; ++k) {
if (count[i][k] > 0) {
printf("%d个\n", count[i][k]);
}
}
}
} else {
printf("\n -1\n");
}
return 0;
}
```
这里我们将 `count` 数组改为二维数组,其中第一维表示硬币的面值,第二维表示要找的钱数。在计算 `c[k]` 的值时,如果发现使用当前硬币面额可以更新 `c[k]` 的值,就将 `count[i]` 数组清零,然后将当前硬币的个数记录到 `count[i][k]` 数组中,如果使用当前硬币面额的个数和原来相等,则将当前硬币的个数记录到 `count[i][k]` 数组中即可。最后输出每种面额的硬币各用了多少个即可。
阅读全文