【C++编程题】最少钱币数（动态规划，递归）
【问题描述】这是⼀个古⽼⽽⼜经典的问题。⽤给定的⼏种钱币凑成某个钱数，⼀般⽽⾔有多种⽅式。例如：给定了 6 种钱币⾯值为 2、5、10、20、50、100，⽤来凑 15 元，可以⽤ 5 个 2 元、1个 5 元，或者 3 个 5 元，或者 1 个 5 元、1个 10 元，等等。显然，最少需要 2 个钱币才能凑成 15 元。
你的任务就是，给定若⼲个互不相同的钱币⾯值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。
【输⼊形式】输⼊可以有多个测试⽤例。每个测试⽤例的第⼀⾏是待凑的钱数值 M（1 <= M<= 2000，整数），接着的⼀⾏中，第⼀个整数 K（1 <= K <= 10）表⽰币种个数，随后是 K个互不相同的钱币⾯值 Ki(1 <= Ki <= 1000)。输⼊ M=0 时结束。
【输出形式】每个测试⽤例输出⼀⾏，即凑成钱数值 M 最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是⽆限多的。
【样例输⼊】
15
6 2 5 10 20 50 100
1
1 2
【样例输出】
2
Impossible
【思路】
这是⼀道由基础的最⼩钱币数改来的，原题⽬只有固定⼏种⾯额，现在有n种~
dp[i]表⽰凑到i元所需要的最少钱币数
举个例⼦：⾯额为1，3，5的钱币，凑成15元
dp[1]=1,  dp[3]=1,  dp[5]=1  这三个是初始值，凑成1，3，5元都只需要1张钱币，由这三个推出所有dp[i]
那么求⼀个dp[ 20 ]，它是怎么凑出20元呢？
只有3种可能：最后⼀张钱只能是1，3，5元，因此只能是：
1.已经凑好了19元，再多加 1张1元
2.已经凑好了17元，再多加1张 3元
3.已经凑好了15元，再多加1张 5元
这三种情况。因此 dp[20] = min( d[19]+1,dp[17]+1, dp[15]+1 );
⽽dp[15], dp[17], dp[19] 同样的道理⽤前⾯已知的dp求出来
如何判断能否凑出？
初始化全部为很⼤的数量，如果求出的dp[M]超过了M⾃⾝，说明是以不可能的路径“凑”出的M元
也要做⼀些限制，⽐如：如果M⼩于最⼩⾯额，当然是不能凑出的
如果还是不太清楚，下⾯这个B站视频讲得很清晰：（视频前⾯有点⼴告请忽视）
BV1xb411e7ww
【AC代码】
#include<string>
#include<iostream>
#include<sstream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 100000
int dp[2500];  //dp[i] 为凑到i元钱所需要的最⼩钱数
int mark[2500];
int main(){
编程递归函数int M;
while(cin>>M && M){
for(int i=0;i<2500;i++) dp[i]=maxn;
memset(mark,0,sizeof(mark)); //初始化dp数组和标记数组，标记数组是为了跳过【⾯值=当前⾦额】的情况
int n;
cin>>n;
int money[n];
for(int i=0;i<n;i++) cin>>money[i];
sort(money,&money[n]);  //先对⾯额排个序
for(int i=0;i<n;i++){
dp[money[i]]=1;
mark[money[i]]=1;  //标记⾯额值，等会⼉在dp过程中直接跳过他们（他们的值已经固定为1了）
}
if(M<money[0]) {
cout<<"Impossible"<<'\n';  //如果⼩于最⼩⾯值不能兑换
continue;
}
for(int i=money[0];i<=M;i++) {  //从最⼩⾯值开始遍历
if(!mark[i]){
vector<int> v;
for(int k=0;k<n;k++){
if(money[k]<i){
v.push_back(dp[i-money[k]]+1);  //看看dp[i]可能从哪个前⾯的dp⽽来
//把所有可能加⼊vector
}else {
break;
}
}
sort(v.begin() ,v.end() );    //在所有可能中到使得dp[i]最⼩的那种
dp[i]= v[0];
v.clear() ;
}
}
if(dp[M]>=100000) cout<<"Impossible"<<'\n';    //由不可能的路径⽽来
else cout<<dp[M]<<'\n';
}
}
【写在后⾯】
觉得对你有帮助的话记得⼀键三连哦~（误
相关题⽬放在了【HNU CJ】专栏
如果有啥问题可以评论留⾔或者私我哦~

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。