硬币

如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？

这个题贪心就可解决

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int n,sum;
int main()
{
    scanf("%d",&n);
    while(n>=5)
    {
        n-=5;
        sum++;
    }
    while(n>3)
    {
        n-=3;
        sum++;
    }
    while(n>0)
    {
        n-=1;
        sum++;
    }
    printf("%d",sum);
    return 0;
 } 

如果我们有面值为2元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？

 使用动归

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n,sum,f[10000]; 
int main()
{
    scanf("%d",&n);
    f[0]=0;
    for(int i=1;i<=n;i++)
       {
           f[i]=100000;
           f[2]=1;
        f[3]=1;
        f[5]=1;
        if(i>=2)
           f[i]=min(f[i-2]+1,f[i]);
        if(i>=3)
           f[i]=min(f[i-3]+1,f[i]);
        if(i>=5)
           f[i]=min(f[i-5]+1,f[i]);
       }
    printf("%d",f[n]);
    return 0;
}