b511: 換銅板

內容

輸入不同面值的銅板，然後輸入一個金額，將全部可能的找零方式列出。譬如有 3 種銅板面值分別是 1 元、5 元、10 元，假設要湊出 17 元，如果把找零方法表示成 “(1 元個數,5 元個數,10 元個數)”，總共會有下列幾種方法

(2,1,1)
(2,3,0)
(7,0,1)
(7,2,0)
(12,1,0)
(17,0,0)

排列順序的規則: 例如 (7,0,1) 先於 (12,1,0) 因為 7 比 12 小；而 (7,0,1) 和 (7,2,0) 的順序，因為第一個數目 7 和 7 相等，這時候就要比第二個數目，而由於 0 小於 2 所以 (7,0,1) 先於 (7,2,0)。

輸入

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

銅板面值和金額都是不超過 100 的正整數。（補充 by liouzhou_101）

3
1 5 10
17

輸出

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

(2,1,1)
(2,3,0)
(7,0,1)
(7,2,0)
(12,1,0)
(17,0,0)

解題思路

把它想像成一棵樹，錢的種類數就是層數，錢的數量則是該子節點的數量，以範例測資為例就會變成 :

[]             (根)
[0 1 2 ... 17] (1元 => 個這層有17節點)
[0 1 2 ... 4]  (5元 => 這層有 17 * 4 = 68 個節點)
[0 1]          (10元 => 這層有 68 * 2 = 136 個節點)

如果依序走訪第 2 第 3 第 0 個節點，那(2,3,0)走訪的結果就為 1 * 2 + 5 * 3 + 10 * 0 = 17 元。

由於輸出排序為

(0,0,0) → (0,0,n) → (0,n,n) → (n,n,n)

所以用前序走訪的方式來走訪整個樹，到底部時就判斷走訪的結果是否為目標值。

剪枝 :

因為每在走訪時同一層的結果只會越來越大，所以當該層的走訪結果大於目標值時，當前和其後面的節點都必大於目標值，故可直接返回上一層。

同樣以範例測資為例：

當走訪至 (10,2) 節點時，因為是採用前序走訪的方式，所以 (10,1) 和其子節點都已經走訪過了，只剩 (10,2) , (10,3) , (10,4) 沒走訪，而 (10,2) 節點結果為 1 _ 10 + 5 _ 2 = 25，超過目標值 17，而 (10 , 3) , (10 , 4) 節點又大於 (10 , 2)，也就必定大於目標值，所以可以直接返回上一層 (也就是從 (11) 開始繼續走訪 )。

完整程式碼

AC (2ms, 112KB)

#include <stdio.h>

const char strfmt[6][20] = { "" , "(%d)\n" , "(%d,%d)\n" , "(%d,%d,%d)\n" , "(%d,%d,%d,%d)\n"  , "(%d,%d,%d,%d,%d)\n" };
int n, m, max, coin[5], cont[5];

void dfs(int sum, int lv)
{
    for (int i = 0; sum < m; i++)
    {
        if (lv < max)
            dfs(sum, lv + 1);
        sum += coin[lv];
        cont[lv]++;
    }
    if (sum == m)
        printf(strfmt[n], cont[0], cont[1], cont[2], cont[3], cont[4]);
    cont[lv] = 0;
}

int main()
{
    while (scanf(" %d", &n) == 1)
    {
        for (int i = 0; i < n; i++)
            scanf(" %d", &coin[i]);
        scanf(" %d", &m);
        max = n - 1;
        dfs(0, 0);
    }
    return 0;
}