1132: 最少硬币问题

Time Limit: 1500 ms   

Memory Limit: 10000 kB  

Total Submit :  

(187 users)   

Accepted Submit :  

(132 users)   

Page View : 9030 

Font Style:

设有n 种不同面值的硬币，各硬币的面值存于数组T［1:n］中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins［1:n］中。

对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。

编程任务：

对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，编程计算找钱m的最少硬币数。

Input

输入包括多组测试数据，每组输入的第一行中只有1 个整数给出n的值,第2 行起每

行2 个数，分别是T[j]和Coins[j]。每组输入最后1 行是要找的钱数m。

Output

对于每组输入数据，输出一行，即计算出最少硬币数。问题无解时输出-1。

Sample Input

31 32 35 318

Sample Output

5

Source

1 /*类似无穷硬币 ,wa  2 */ 3 #include 
      
        4 #include 
       
         5 using namespace std; 6  7 const int maxn = 15; 8 int coins[maxn],num[maxn]; 9 int n,money;10 int ans[20010];11 12 int main()13 {14     int i,j,k;15     int a, b;16     while(cin>>n)17     {18         int max = -1;19         memset(ans,-1,sizeof(ans));20         for(i=0; i
        
         >a>>b;23             coins[i] = a;24             if(a>max)25                 max = a;26             num[i] = b;27         }28         cin>>money;29         //最好先排序30         for(k=1; k<=money; k++)31         {32             int min = 0x7fffffff; 33             for(i=0; i
         
          =coins[i])//不是coins[j] 37                     {38                         int temp = ans[k-coins[i]] + 1;39                         if(min>temp)40                             min = temp;41                     }42                 }43             ans[k] = min;44         }45         if(ans[money]>=(money/max))46             cout<
          
           <
          
         
        
       
      

#include 
      
       #include 
       
        using namespace std;const int maxn = 15;int coins[maxn],num[maxn];int n,money;int ans[maxn][20010];int main(){    int i,j,k;    int a, b;    while(cin>>n)    {        memset(ans,0,sizeof(ans));        for(i=0; i
        
         >a>>b;            coins[i] = a;            num[i] = b;        }        cin>>money;                for(i=0; i<=money; i++)        {            if(i%coins[0]==0)                ans[0][i] = i/coins[i];            else                ans[0][i] = INT_MAX;        }        for(i=1; i
        
       
      

/*类似无穷硬币 ,wa */#include 
      
       #include 
       
        using namespace std;const int maxn = 15;int coins[maxn],num[maxn];int n,money;int ans[20010];int main(){    int i,j,k;    int a, b;    while(cin>>n)    {        int max = -1;        memset(ans,0,sizeof(ans));        for(i=0; i
        
         >a>>b;            coins[i] = a;            if(a>max)                max = a;            num[i] = b;        }        cin>>money;        //最好先排序        for(k=1; k<=money; k++)        {            int min = 0x7fffffff;             for(i=0; i
         
          =j*coins[i])//不是coins[j]                     {                        int temp = ans[k-j*coins[i]] + j;                        if(min>temp)                            min = temp;                    }                }            ans[k] = min;        }        if(ans[money]>=(money/max))            cout<
          
           <