要求：

有n种硬币，面值分别为v1,v2,v3,,,,,vn,数量无限。输入非负整数n，选用硬币，使其和为n，要求输出最少的硬币组合。
这里假设n=5，其它情况也一样的。

准备工作

假设只有5种面值的硬币：1，5，10，25，50
tepy[5]={1,5,10,25,50}每种硬币的面值
mi[i]：表示金额为i最少需要多少个硬币
path[i]：表示金额为i需要的最后一个硬币的面额，便于后面输出方案，方案里一定有path[i]，下一个一定是path[i-path[i]],因为path一定会保证当前最优

思路：

状态：mi[i]:表示金额为i最少需要多少个硬币
mi[i]=mi[i-tepy[j]]+1;表示金额i可以由金额i-tepy[j]加上一块面额为tepy[j]的硬币得到

代码：

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int type[5]={1,5,10,25,50};//所有面值的硬币 
int mi[251];                //每个数值需要的最小硬币数
int path[251];                //每个数值需要的最后一个硬币面值 
void solve() {
    for(int i=1;i<251;++i)    //初始化 
        mi[i]=300;
    mi[0]=0;
    for(int i=0;i<5;++i) 
    for(int j=type[i];j<251;++j)
        if(mi[j]>mi[j-type[i]]+1) {
            path[j]=type[i];      //在每个金额上记录路径，即金币的面值 
            mi[j]=mi[j-type[i]]+1;//递推式 
        }
}
void print(int s) {
    while(s) {
        cout<<path[s]<<" ";
        s-=path[s];
    }
    cout<<endl;
}//打印硬币组合 
int n;
int main() {
    js;
    solve();
    while(cin>>n) {
        cout<<mi[n]<<endl;
        print(n);
    }
    return 0;
}