b511

輸入說明 ：

輸入有三行 第一行一個數字 N 代表有幾種不同面值的銅板 (N <= 5) 第二行就是 N 個整數，表示 N 種對應的銅板面值 第三行一個數字是要需要找零的金額

輸出說明 ：

列出每一種找零方法，用括號框住每個銅板的數量，數量之間用逗號隔開，每一種找零方法後面要換行。不同的找零方法的排列順序要依照題目的規定。

這題是學長教我的

先定義一個結構,一組可能的答案,這個結構放每種硬幣的可能性

在來定義這個結構怎麼比大小(運算子多載)

接著用遞迴的方式來找答案

對於每一種硬幣最多取到它的數目加種 = 要求的數值

比方說1,5,10 去湊17

10最多一個 ,5最多三個 ,1最多17個

所以用while迴圈來控制每一輪要做幾個

最後排序a的vector即可

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int N, cash;
int v[5];

struct amount
{
    int coins[5];
    int i;

    amount()
    {    
        for(i=0;i<N;i++)
            coins[i]=0;
    }    

    bool operator < (const amount &a) const
    {
        for(int j=0;j<N;j++) 
        {
            if( coins[j] < a.coins[j] ) return true;
            else if(coins[j] > a.coins[j]) return false;
        }
        return false;
    }
}; 

vector <amount> vnum;
void dfs(int remains,amount a,int cur)
{
    if(cur==N)
    {
        if(remains==0)
        {
            vnum.push_back(a);
        }    
        return ;
    }

    while(remains>=0)
    {
        dfs(remains,a,cur+1);

        remains -= v[cur];
        a.coins[cur]+=1; 
    }
    return ;
}
int main()
{
    scanf("%d",&N);
    int i,j;
    for(i=0;i<N;i++)
        scanf("%d",&v[i]);
    scanf("%d",&cash);

    amount temp;
    dfs(cash,temp,0);

    sort(vnum.begin(),vnum.end());

    for(i=0;i<vnum.size();i++)
    {
        printf("(");

        for(j=0;j<N-1;j++)
        {
            printf("%d,",vnum[i].coins[j]);
        }
        printf("%d",vnum[i].coins[N-1]);
        printf(")\n");    

    }
    return 0;
}