动态规划 最少硬币问题
[实验目的] 练习动态规划算法 [实验题目] 设有 n 种不同面值的硬币，各硬币的面值存于数组 T［1:n］中。现要用这些 面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组 Coins［1:n］中。 对任意钱数 0≤m≤20001，设计一个用最少硬币找钱 m 的方法。
#include <stdio.h> #include<string.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 w[11]; int m; //要找的钱数 m void init() { int i; printf("输入硬币的面值种数："); scanf_s("%d",&n); printf("输入硬币面值及其此面值硬币的个数：\n"); for (i = 0; i < n; ++i) scanf_s("%d %d", &T[i], &Coins[i]); printf("输入要找的钱数："); scanf_s("%d", &m); } int main() { int i, j, k; 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) c[k] = min(c[k], c[k - T[i]] + 1); } } if (c[m] != INF) { int t,q=c[m],p=m; printf("最少硬币个数为：%d\n", c[m]); for (i = m; i>=0; i--) { if (c[i] == c[p]-1) { t = p-i;//记录所选的硬币 for (j = 0; j < n; j++) { if (t == T[j])//找到所选的硬币 w[j]++;//进行硬币计数 } p = i; } } for (i = 0; i < n; i++) { if(w[i]!=0)//如果该硬币没有被选，则为零，不用输出 printf("面值为%d的硬币有%d个\n",T[i],w[i]); } } else printf("\n -1\n"); return 0; }截图： 这是我大二的实验，希望对大家有帮助，代码我是在vs写的，运行都是对的，要是不对就把scanf_s 改回scanf_s.
