最少硬币问题
最少硬币问题(动态规划)
设有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
代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 0x3f3f3f3f
int dp[20005];
int main(){
int n,m,T[20005],Coins[20005];
cin>>n;
for(int i=0;i<n;i++){
cin>>T[i]>>Coins[i];
}
cin>>m;
dp[0]=0; //初始化dp数组
for(int i=1;i<=m;i++){
dp[i]=MAXN;
}
for(int i=0;i<n;i++){ //硬币的各个数值
for(int j=1;j<=Coins[i];j++){ //硬币的数量
for(int k=m;k>=T[i];k--){
dp[k]=min(dp[k],dp[k-T[i]]+1);
}
}
}
if(dp[m]<m){
cout<<dp[m];
}else{
cout<<-1;
}
return 0;
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 时间海!
评论