HDU-1284 钱币兑换问题(枚举)(完全背包)

钱币兑换问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 13353 Accepted Submission(s): 8062

Problem Description

在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

Input

每行只有一个正整数N，N小于32768。

Output

对应每个输入，输出兑换方法数。

Sample Input

2934

12553

Sample Output

718831

13137761

Author

SmallBeer(CML)

Source

杭电ACM集训队训练赛（VII）

Recommend

lcy

方法一：枚举

刚开始想的是直接枚举，但想想o(n^3) 肯定会超时。然后想到三分和两分数量确定后剩下必定是一分，试了一下o(n^2) 还是TLE。

再后来发现只要考虑三分的数量即可，剩下的除于2就是可以取2分的可能。即sum+=(n-i3)/2。

例如n=10时，i等于1时，n-3i即为取完一个3分后剩下的总金额，将这个金额除于2即为可能取2分的情况，在这里，(n-i*3)/2=3，也就是说你可以取1枚2分的，或者2枚，或者三枚，一共三种可能。

但你也许已经注意到了，这样并没有考虑到不取2分的情况。所以我们将sum的初值赋为n/3+1，即为只有3分和1分的情况。

代码实现

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int sum=n/3+1;
        for(int i=0;i<=n/3;i++)
        {
            sum+=(n-i*3)/2;
        }
        printf("%d\n",sum);
    }
}
           

方法二：完全背包

其实一开始并没有想到用背包的(其实是因为那时我根本不会背包2333)，后来看见好多题解提到了背包。感觉可以用完全背包来考虑。

输入的n即为背包容量，数组p记录当前状态下的方法总数。因为每种硬币可以无限取所以第二个for用顺序。(不会背包的同学可以看看这篇文章 http://www.wutianqi.com/?p=539)

代码实现

#include<bits/stdc++.h>
using namespace std;

int p[33000];
int main()
{
    p[0]=1;
    for(int i=1;i<=3;i++)
        for(int j=i;j<33000;j++)
            p[j]+=p[j-i];
    int n;
    while(cin>>n)
    {
        cout<<p[n]<<endl;
    }
}