数据结构与算法课程设计 最少硬币问题

Question

最少硬币问题

问题描述
设有n种不同面值的硬币，各个硬币的面值存于数组T[1:n]中，现在要用这些面值的硬币来找钱，可以使用的各种面值的硬币个数存于数组Coin[1:n]中。对于任意钱数m，设计一个用最少硬币找钱m的方法。
基本要求
（1）数据输入：由文件input.txt提供输入数据，文件的第一行中只有一个整数给出n的值，第二行起每行2个数，分别是T[j]和Coin[j]，最后一行是要找的钱数m。
结果输出：将计算出的最少硬币数输出到文件output.txt，问题无解时输出-1。问题有解时，还需输出具体的支付方案。
(2) 用动态规划来求解该问题。
(3) 输入文件示例 输出文件示例
input.txt output.txt
3 5
1 3 2
2 3 0
5 3 3
18
测试数据
由读者给定若干实例。

Answer 1

Source

//code c++ 调试环境 vc++ 6.0

//代码实现:

#include <stdio.h>
#include <algorithm>

using namespace std ;

struct Coin
{
int value ;
int num ;
}T[11] ;

int comp(Coin a ,Coin b )
{
return a.value <= b.value ;
}

int main()
{
int i ;
int n ;
int m ,sum ;
while(scanf("%d",&n ) != EOF)
{
for( i = 0 ; i < n ; i ++ )
{
scanf("%d %d",&T[i].value , &T[i].num );
}
scanf("%d",&m ) ;
sort(T,T+n ,comp );
sum = 0 ;
int k = -1 ;
for( i = n-1 ; i >=0 ; i-- )
{
if( T[i].value <= m )
{
k = i ;
break;
}
}
for( i = k ; i >= 0 ; i -- )
{
while( T[i].num > 0 && m >= T[i].value )
{
sum ++ ;
m -= T[i].value ;
}
if( m <= 0 )
break ;
}
printf("%d\n",sum ) ;
}
return 0 ;
}

参考资料：http://blog.sina.com.cn/s/blog_5cd377280100ay9g.html

Answer 2

现在懒得动脑子。