硬币找零

2013年11月21日3,8410

题目描述

设有n种（n<=20）不同面值的硬币，各硬币的面值存于数组T[1..N]中，数据中至少有一枚硬币面值为1，现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数不限，请计算找出钱数m(1<=m<=10000)的最少硬币个数。
输入：第一行为n种硬币和要找的钱数m ;
第二行为分别为n种硬币的面值t1,t2…tn
输出：最小的硬币个数

样例输入

4 100
1 2 5 10

1 2	4 100 1 2 5 10

样例输出

10

代码

#include<iostream>
#include<cstring>
using namespace std;
int n,m,a[21],f[10001];
int main()
{
    memset(f,127,sizeof(f));
    f[0]=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
       cin>>a[i];
    for(int i=1;i<=n;i++)
       for(int j=a[i];j<=m;j++)
          f[j]=min(f[j],f[j-a[i]]+1);
    cout<<f[m];
    return 0;
    }

#include<iostream>

#include<cstring>

using namespace std;

int n,m,a[21],f[10001];

int main()

{

memset(f,127,sizeof(f));

f[0]=0;

cin>>n>>m;

for(int i=1;i<=n;i++)

cin>>a[i];

for(int i=1;i<=n;i++)

for(int j=a[i];j<=m;j++)

f[j]=min(f[j],f[j-a[i]]+1);

cout<<f[m];

return 0;

}

« NOIP2006金明的预算方案机器分配 »

hzwer.com _ Home | http://hzwer.com

硬币找零

题目描述

样例输入

样例输出

代码

分类目录

热门文章

Myfriends

近期评论