风的方向 厚德致远，博学敦行！

```3
1 3
2 3
5 3
18```

## Sample Output

`5`
`         动态规划题。`
`代码如下：`
```#include<cstdio>int main(){    int t[11],coins[11],c[11][20002];//c[i][j]前i种硬币找j块钱最少硬币数    int i,j,n,m,k;    while(scanf("%d",&n)!=EOF)    {        for(i=1;i<=n;i++)        {            scanf("%d %d",&t[i],&coins[i]);        }        scanf("%d",&m);        for(i=1;i<=n;i++)        //初始化            for(j=0;j<=m;j++)            {                if(j==0)                    c[i][j]=0;                else if(i==1)                      if(j%t[i]==0&&j/t[i]<=coins[i])                        c[1][j]=j/t[i];                    else                        c[1][j]=1000000;                else                    c[i][j]=1000000;            }        for(i=2;i<=n;i++)        //构造c数组            for(j=1;j<=m;j++)                for(k=0;k<=coins[i];k++)                {                    if(c[i][j]>(c[i-1][j-k*t[i]]+k)&&(j-k*t[i])>=0)                            c[i][j]=c[i-1][j-k*t[i]]+k;                }        if(c[n][m]!=1000000)        {            printf("%d\n",c[n][m]);        }        else            printf("-1\n");    }    return 0;}
```
`题目地址：http://acm.nankai.edu.cn/p1132.html`
posted on 2010-09-17 13:32 jince 阅读(2170) 评论(0)  编辑 收藏 引用 所属分类: Questions