1132: 最少硬币问题
Time Limit: 1500 ms Memory Limit: 10000 kB
Total Submit : 909 (187 users) Accepted Submit : 241 (132 users) Page View : 9030
设有n 种不同面值的硬币，各硬币的面值存于数组T［1:n］中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins［1:n］中。
对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。
编程任务：
对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，编程计算找钱m的最少硬币数。
Input
输入包括多组测试数据，每组输入的第一行中只有1 个整数给出n的值,第2 行起每
行2 个数，分别是T[j]和Coins[j]。每组输入最后1 行是要找的钱数m。
Output
对于每组输入数据，输出一行，即计算出最少硬币数。问题无解时输出-1。
Sample Input
3 1 3 2 3 5 3 18
Sample Output
5
Source
View Code
1 /*类似无穷硬币 ,wa 2 */ 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 15; 8 int coins[maxn],num[maxn]; 9 int n,money; 10 int ans[20010]; 11 12 int main() 13 { 14 int i,j,k; 15 int a, b; 16 while(cin>>n) 17 { 18 int max = -1; 19 memset(ans,-1,sizeof(ans)); 20 for(i=0; i<n; i++) 21 { 22 cin>>a>>b; 23 coins[i] = a; 24 if(a>max) 25 max = a; 26 num[i] = b; 27 } 28 cin>>money; 29 //最好先排序 30 for(k=1; k<=money; k++) 31 { 32 int min = 0x7fffffff; 33 for(i=0; i<n; i++) 34 for(j=1; j<=num[i]; j++) 35 { 36 if(k>=coins[i])//不是coins[j] 37 { 38 int temp = ans[k-coins[i]] + 1; 39 if(min>temp) 40 min = temp; 41 } 42 } 43 ans[k] = min; 44 } 45 if(ans[money]>=(money/max)) 46 cout<<ans[money]<<endl; 47 else 48 cout<<"-1"<<endl; 49 50 } 51 52 return 0; 53 }
View Code
#include <iostream> #include <cstring> using namespace std; const int maxn = 15; int coins[maxn],num[maxn]; int n,money; int ans[maxn][20010]; int main() { int i,j,k; int a, b; while(cin>>n) { memset(ans,0,sizeof(ans)); for(i=0; i<n; i++) { cin>>a>>b; coins[i] = a; num[i] = b; } cin>>money; for(i=0; i<=money; i++) { if(i%coins[0]==0) ans[0][i] = i/coins[i]; else ans[0][i] = INT_MAX; } for(i=1; i<n; i++) for(j=0; j<=money; j++) if(j<coins[i]) ans[i][j] = ans[i-i][j]; else ans[i][j] = min(ans[i-i][j],ans[i-1][j-coins[i]] + 1); cout<<ans[n-1][money]<<endl; } return 0; }
View Code
/*类似无穷硬币 ,wa */ #include <iostream> #include <cstring> using namespace std; const int maxn = 15; int coins[maxn],num[maxn]; int n,money; int ans[20010]; int main() { int i,j,k; int a, b; while(cin>>n) { int max = -1; memset(ans,0,sizeof(ans)); for(i=0; i<n; i++) { cin>>a>>b; coins[i] = a; if(a>max) max = a; num[i] = b; } cin>>money; //最好先排序 for(k=1; k<=money; k++) { int min = 0x7fffffff; for(i=0; i<n; i++) //dp[j]=MIN(dp[j],dp[j-k*coins]+k), for(j=1; j<=num[i]; j++)//此时ans初始化为-1答案少一 { if(k>=j*coins[i])//不是coins[j] { int temp = ans[k-j*coins[i]] + j; if(min>temp) min = temp; } } ans[k] = min; } if(ans[money]>=(money/max)) cout<<ans[money]<<endl; else cout<<"-1"<<endl; } return 0; }
