C :

#include<stdio.h>
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;
}

C++ :

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N;
    int money[11],coins[11];
    int dp[20005];
    scanf("%d",&N);
    for(int i = 0 ; i < N ; i++)
        scanf("%d%d",&money[i],&coins[i]);
    int s;
    scanf("%d",&s);
    for(int i = 1 ; i <= s ; i++)
        dp[i] = 20005;
    for(int i = 0 ; i < N ; i++)
    {
        for(int j = 1 ; j <= coins[i] ; j++)
        {
            for(int k = s ; k >= money[i] ; k--)
                dp[k] = min(dp[k],dp[k-money[i]]+1);
        }
    }
    printf("%d\n",dp[s]<s?dp[s]:-1);
    return 0;
}