1236 . 組合和2世

題解  |  Anpig  |  2020-11-28  |  1.2k  |  4 Minutes

題目

龍我因為期中考考不好，決定奮發圖強，開始練習遞迴的題目，
但才剛看到題目就受不了了，立刻拜託了你幫他看看這題怎麼寫，
雖然你和他不熟，但看在同學一場，還是幫一下他吧。
「請找出能加總成目標數字的所有組合，
且所有可以用的數字都可以『無限次』的被使用。」

輸入說明

首先會是 1 個正整數 N（0 < N < 10），表示測資的數量。
接下來每 2 行會是一筆測資，第 1 行為 1 個正整數 A（< 100），
代表目標的數字，第 2 行是一串嚴格遞增的正整數（< 20，最多 10 個數字），
表示可以用的數字，會以 0 結尾（0 不包含在可以用的數字裡）。

輸出說明

對每筆測資，輸出「finish」（有解）或「no solution」（無解）。
若有解，則在 finish 之前輸出可以加總成目標數字的所有組合，
有用到越多越小的數字的組合排前面，每個解各佔 1 行。

想法

首先開個陣列int arr[21];紀錄給定能用的數字；
而int ans[101];紀錄已選的數字，
長度開101是因為A < 100，且能使用的數字都是正整數，
所以最長的情況也就用 99 個1來達成，開大一點是我個人的習慣。
（其實也可以開21，改存每個數用了幾次，但我當初沒想到，現在也懶得改。）

現在開始建造遞迴函數，給它三個參數，
分別是：

  1. n： 現在要選「能選的數字」中的第幾個數字
  2. sum： 我們想要得到的目標（組合和）
  3. used： 已經用過幾個數（最後需要輸出幾個數）

再來我們要設定遞迴的中止點，
可能的中止點有：

  1. 目前的組合和剛好跟目標一樣了（sum == A）
  2. 目前的組合和超過目標了（sum > A）
  3. 沒有能用的數了（n >= N）
1
2
3
4
5
6
7
8
9
10
if (sum == A) {
    havesol = 1;
    for (int i = 0; i < used; i++) {
        printf("%d ", ans[i]);
    }
    printf("\n");
    return;
}
if (sum > A) return;
if (n >= N) return;

要注意 1. 的情形因為題目有要求判斷有沒有解，
所以我們這時候也要把解的狀態改成有解（第 2 行）。

如果遞迴還沒結束，那我們得想接下來要怎麼做。

我以前聽一位老師講過一句話，不過我忘記是誰了，
他說：「先相信你的遞迴是對的，再來想要怎麼做。」
所以我先相信我下一次遞迴時它會自己幫我檢查錯誤，
先把現在的第s個數存進組合裡再說（ans[used] = arr[n];），
事實上它的確會這麼做，因為我們在上面設定了中止點。

再來，因為題目說每個數字都可以用無限次，
所以我們尋找第n個數字繼續使用的可能，
dfs(n, sum + arr[n], used + 1);。

然而，如果下一次遞迴發現把第n個數加進去行不通，
就得尋找使用下一個數（第n + 1個數）的可能，
不過因為arr[21]這個陣列是嚴格遞增數列，
所以其實在這一層第n個不行的話，第n + 1個一定也不行，
這時候就會return了，但是到了上一層的話，
第n + 1個是有可能被使用的，
所以下面這一行（第 14 行）其實是寫給上一層看的。
dfs(n + 1, sum, used);

遞迴函數：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int n, int sum, int used) {
    if (sum == A) {
        havesol = 1;
        for (int i = 0; i < used; i++) {
            printf("%d ", ans[i]);
        }
        printf("\n");
        return;
    }
    if (sum > A) return;
    if (n >= N) return;
    ans[used] = arr[n];
    dfs(n, sum + arr[n], used + 1);
    dfs(n + 1, sum, used);
    return;
}

寫完遞迴其實就寫完了，最後main函數裡的輸入輸出搞一搞就完成了。

完整程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
int A, arr[21], N, havesol = 0, ans[21];
void dfs(int n, int sum, int used) {
    if (sum == A) {
        havesol = 1;
        for (int i = 0; i < used; i++) {
            printf("%d ", ans[i]);
        }
        printf("\n");
        return;
    }
    if (sum > A) return;
    if (n >= N) return;
    ans[used] = arr[n];
    dfs(n, sum + arr[n], used + 1);
    dfs(n + 1, sum, used);
    return;
}
int main() {
    int T;
    scanf("%d" ,&T);
    while (T--) {
        scanf("%d", &A);
        havesol = 0;
        for (int i = 0; i < 21; i++) {
            int c;
            scanf("%d", &c);
            if (c == 0) {
                N = i;
                break;
            }
            arr[i] = c;
        }
        dfs(0, 0, 0);
        if (havesol == 0) printf("no solution\n");
        else printf("finish\n");
    }
    return 0;
}
tags:  #Formosa OJ #遞迴 #DFS #Backtrack #窮舉
全部展開 回到頂部 移至底部