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;
    }
}