最少硬币问题（c语言实现）

1.1题目
算法实现题3-2 最少硬币问题
★问题描述:设有n种不同面值的硬币,各硬币的面值存于数组T[1:n]中,现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组 Coins[l:n]中。
对任意钱数0≤m≤20 001,设计一个用最少硬币找钱m的方法。
★算法设计:对于给定的1≤n≤10,硬币面值数组T和可以使用的各种面值的硬币个数数组 Coins,以及钱数m,0≤m≤20 001,计算找钱m的最少硬币数。
★数据输入:由文件 Input.txt提供输入数据,文件的第1行中只有1个整数给出n的值,第2行起每行2个数,分别是T[i]和 Coins[j]。最后1行是要找的钱数m。
★结果输出:将计算出的最少硬币数输出到文件 output.txt,问题无解时输出-1。
输入文件示例 输出文件示例
input.txt output. txt
3 5
1 3
2 3
5 3
1 8
1.2分析
因为之前的程序使用了贪心算法，导致更换数据后极有可能误将局部最优解当成全局最优解输出，为保证结果的正确性，改用遍历算法，使用goto语句循环遍历所有可能性。
1.3源代码

#include <iostream>
#include<stdio.h>
void sort(int* p, int* q, int n);
int main()
{
	FILE* fpr, * fpw;
	fopen_s(&fpr, "input.txt","r");
	fopen_s(&fpw, "output.txt", "w");
	int i, j, m, n = 0, s, max, y, nn, z, f = 0, min, k;
	int T[10], Coins[10],b[1000];
	fscanf_s(fpr, "%d", &nn);
	j = z = 0;
	for (i = 0; i < 2 * nn; i++)
	{
		if (i % 2 == 0)
		{
			fscanf_s(fpr, "%d", T + j);//遇到空格或换行自动暂停读
			j++;
		}
		if (i % 2 == 1)
		{
			fscanf_s(fpr, "%d", Coins + z);
			z++;
		}
	}
	fscanf_s(fpr, "%d", &m);
	s = nn;
	printf("共有%d种硬币\n", s);//调试用
	sort(T, Coins, s);
	y = m;
	s -= 1;
aa:	for (i = nn - 1; (i >= 0) && (y != 0); i--)//余数匹配
	{
		for (j = 0; (y >= T[i]) && (j < Coins[i]); j++)
		{
			y -= T[i];
			n += 1;
		}
	}
		if (y == 0)
			b[f++] = n;
		n = 0;
		y = m;
		s -= 1;
		k = T[nn-1];
		T[nn-1] = T[s];
		T[s] = k;
		k = Coins[nn - 1];
		Coins[nn - 1] = Coins[s];
		Coins[s] = k;
		while (s != 0)
			goto aa;
	min = b[0];
	for (i = 0; i < f; i++)
		if (b[i] < min)
			min = b[i];
	printf("总方案数为:%d", min);//调试用
	fprintf(fpw, "%d\n", min);
	fclose(fpr);
	fclose(fpw);
	return 0;
}
void sort(int* p, int* q, int n)//冒泡排序
{
	int i, j, temp;
	for (i = 0; i < n-1; i++)
		for (j = i + 1; j < n; j++)
			if (p[i] > p[j])
			{
				temp = p[i];
				p[i] = p[j];
				p[j] = temp;
				temp = q[i];
				q[i] = q[j];
				q[j] = temp;
			}
}

1.4运行结果

1.5总结

编程完成后应使用大量结果或特殊情况进行验证，以防边界值出现错误。

在文件的数据较为复杂时，不能熟练掌握对文件的操作，继续加油！