|
在现实生活中，我们经常遇到硬币找零的问题，例如，在发工资时，财务人员就需要计算最少的找零硬币数，以便他们能从银行拿回最少的硬币数，并保证能用这些硬币发工资。我们应该注意到，人民币的硬币系统是 $100$，$50$，$20$，$10$，$5$，$2$，$1$，$0.5$，$0.2$，$0.1$，$0.05$，$0.02$，$0.01$ 元，采用这些硬币，我们可以对任何一个工资数用贪心算法求出其最少硬币数。但不幸的是：我们可能没有这样一种好的硬币系统，因此用贪心算法不能求出最少的硬币数，甚至有些金钱总数还不能用这些硬币找零。例如，如果硬币系统是 $40$，$30$，$25$ 元，那么 $37$ 元就不能用这些硬币找零；$95$ 元的最少找零硬币数是 $3$。又如，硬币系统是 $10$，$7$，$5$，$1$ 元，那么 $12$ 元用贪心法得到的硬币数为 $3$，而最少硬币数是 $2$。
你的任务就是：对于任意的硬币系统和一个金钱数，请你编程求出最少的找零硬币数。
输入格式
第一行，两个整数 $N$ 和 $M$，其中 $1\le N \le 50$ 为硬币系统中不同硬币数，$1\le M\le 100000$ 为需要用硬币找零的总数。
第二行为 $N$ 个整数 $a_i\ (1\le a_i \le 1000)$，它们是硬币系统中各硬币的面值。
输出格式
请输出最少的找零硬币数，输入不存在输出 $-1$。
Sample Input
4 12
10 7 5 1
Sample Output
2
答案：
#include<stdio.h>
int min(int i,int j){
? ? if(i<j)return i;
? ? else return j;
}
int main()
{
? ?int n,m,i,j;
? ?scanf("%d %d",&n,&m);
? ?int a[n],dp[m+1];
? ?for(i=0;i<n;i++){
? ? ? ? scanf("%d",&a[i]);
? ?}
? ?dp[0]=0;
? ?for(i=1;i<=m;i++){
? ? ? ? dp[i]=m+1;
? ?}
? ?for(i=1;i<=m;i++){
? ? for(j=0;j<n;j++){
? ? ? ? if(a[j]<=i){
? ? ? ? ? ? dp[i]=min(dp[i],dp[i-a[j]]+1);
? ? ? ? }
? ? }
? ?}
? ?if(dp[m]!=m+1){
? ? ? ? printf("%d",dp[m]);
? ?}
? ?else{
? ? printf("-1");
? ?}
}
（如有优化，请指教）
|