【问题描述】
这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了 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
0
【样例输出】
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】
专栏
如果有啥问题可以评论留言或者私我哦~