最少硬币问题(受限)NK1132

1132: 最少硬币问题

Time Limit: 1500 ms    Memory Limit: 10000 kB  
Total Submit : 909 (187 users)   Accepted Submit : 241 (132 users)   Page View : 9030 

Font Style: Aa Aa Aa

设有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

3
1 3
2 3
5 3
18

Sample Output

5

Source

福建省优质硕士课程《算法设计与分析》教学组

View Code

 1 /*类似无穷硬币 ,wa
 2 */
 3 #include <iostream>
 4 #include <cstring>
 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<n; i++)
21         {
22             cin>>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<n; i++)
34                 for(j=1; j<=num[i]; j++)
35                 {
36                     if(k>=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<<ans[money]<<endl;
47         else
48             cout<<"-1"<<endl;
49
50     }
51
52     return 0;
53 }

View Code

#include <iostream>
#include <cstring>
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<n; i++)
        {
            cin>>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<n; i++)
            for(j=0; j<=money; j++)
            if(j<coins[i])
                ans[i][j] = ans[i-i][j];
            else
                ans[i][j] = min(ans[i-i][j],ans[i-1][j-coins[i]] + 1);
        cout<<ans[n-1][money]<<endl;

    }
    return 0;
}

View Code

/*类似无穷硬币 ,wa
*/
#include <iostream>
#include <cstring>
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<n; i++)
        {
            cin>>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<n; i++)
            //dp[j]=MIN(dp[j],dp[j-k*coins]+k),
                for(j=1; j<=num[i]; j++)//此时ans初始化为-1答案少一
                {
                    if(k>=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<<ans[money]<<endl;
        else
            cout<<"-1"<<endl;

    }

    return 0;
}