[此贴子已经被作者于2018-3-9 15:09编辑过]

程序代码：

//我也是菜鸟，只是按个人的想法写的，也不晓得有没有问题，主要注释了递归的部分
#include <stdio.h>
#include<limits.h>
int ans,Ki[10];                                         //声明两个全局变量ans和Ki，因为他们都会在main中赋值，在makeraise中改变值
void makeraise(int m,int n,int c);
int main(void)
{
    int M,K,i;
    while(scanf("%d",&M)==1&&M>0)
    {
        ans=INT_MAX;
        scanf("%d",&K);
        for(i=0;i<K;++i)
            scanf("%d",&Ki[i]);
        makeraise(M,K,0);    
        if(ans!=INT_MAX)                          
            printf("%d\n",ans);
        else
            printf("Impossible\n");
    }
    return 0;
}
void makeraise(int m,int n,int c)
{
    if(n<=0)                                 //当可选的金币只有0种或小于0种时停止
        return;        
    if(c<ans&&m==0)                          //当钱正好凑齐时，把c赋值给ans
        ans=c;
    if(m>=Ki[n-1])                           //当待凑的钱总数大于等于当前可用最大面值时
    {
        makeraise(m-Ki[n-1],n,++c);          //选择使用当前最大面值金币来凑，计加一步
        --c;                                 //凑钱失败的话加的一步取消，选择下个方式来凑
        makeraise(m,--n,c);                  //不选择当前最大的面值金币，--n表示Ki的最后一个数组元素不要了
        ++n;                                 //如果这个凑钱方法失败，就不取消最大面值金币。（不过如果两个
    }                                        //方法都失败就Impossible了，所以没有++n应该也没关系）
    else
        if(m>0)                              //如果当前待凑的钱总数小于当前最大面值金币但大于0时
        {
            makeraise(m,--n,c);              //用第二大面值的金币来凑钱
            ++n;                             //如果凑钱失败就不取消最大面值金币（和上面一样没有++n应该也没问题）
        }
    return;
}