3729 - 最少硬币问题
设有n 种不同面值的硬币，各硬币的面值存于数组T［1:n］中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins［1:n］中。
对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。
编程任务：
对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，编程计算找钱m的最少硬币数。
题目输入
输入包括多组测试数据，每组输入的第一行中只有1 个整数给出n的值,第2 行起每
行2 个数，分别是T[j]和Coins[j]。每组输入最后1 行是要找的钱数m。
题目输出
对于每组输入数据，输出一行，即计算出最少硬币数。问题无解时输出-1。
输入/输出样例
题目输入
3 1 3 2 3 5 3 18
题目输出
5
提示
难度略高的硬币问题
C语言解答
#include<stdio.h> int main() { int t[11],coins[11],c[11][20002];//c[i][j]前i种硬币找j块钱最少硬币数 int i,j,n,m,k; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) { scanf("%d %d",&t[i],&coins[i]); } scanf("%d",&m); for(i=1;i<=n;i++) //初始化 for(j=0;j<=m;j++) { if(j==0) c[i][j]=0; else if(i==1) if(j%t[i]==0&&j/t[i]<=coins[i]) c[1][j]=j/t[i]; else c[1][j]=1000000; else c[i][j]=1000000; } for(i=2;i<=n;i++) //构造c数组 for(j=1;j<=m;j++) for(k=0;k<=coins[i];k++) { if(c[i][j]>(c[i-1][j-k*t[i]]+k)&&(j-k*t[i])>=0) c[i][j]=c[i-1][j-k*t[i]]+k; } if(c[n][m]!=1000000) { printf("%d\n",c[n][m]); } else printf("-1\n"); } return 0; }
C++解答
#include <bits/stdc++.h> using namespace std; int main() { int N; int money[11],coins[11]; int dp[20005]; scanf("%d",&N); for(int i = 0 ; i < N ; i++) scanf("%d%d",&money[i],&coins[i]); int s; scanf("%d",&s); for(int i = 1 ; i <= s ; i++) dp[i] = 20005; for(int i = 0 ; i < N ; i++) { for(int j = 1 ; j <= coins[i] ; j++) { for(int k = s ; k >= money[i] ; k--) dp[k] = min(dp[k],dp[k-money[i]]+1); } } printf("%d\n",dp[s]<s?dp[s]:-1); return 0; }
提示
难度略高的硬币问题