PAT 1068 Find More Coins：01 背包記錄路徑輸出最小字典序解

題目大意

給定 N (≤ 10⁴) 枚硬幣面值和目標金額 M (≤ 10²)，選若干硬幣（每枚最多用一次）湊成 M。若多解，輸出字典序最小的面值序列（非遞減序）。無解輸出 No Solution。

核心思路：01 背包 + 路徑記錄

• dp[i][j]：前 i 枚硬幣湊成金額 j 的最大值（實際為是否可達）
• 為輸出字典序最小解，硬幣降序排列，決策時優先「不選」再「選」，回溯時自然得到最小字典序
• flag[i][j] 記錄第 i 枚硬幣湊 j 時是否被選

C++ 代碼

#include 
using namespace std;
const int MAXN = 10005, MAXM = 105;
int v[MAXN][MAXM], flag[MAXN][MAXM], a[MAXN];
int main() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1, greater()); // 降序
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (j < a[i] || v[i-1][j-a[i]] + a[i] < v[i-1][j]) {
                v[i][j] = v[i-1][j]; // 不選
            } else {
                v[i][j] = v[i-1][j-a[i]] + a[i]; // 選
                flag[i][j] = 1;
            }
        }
    }
    
    if (v[n][m] == m) {
        vector res;
        while (m > 0) {
            while (!flag[n][m]) --n;
            res.push_back(a[n]);
            m -= a[n--];
        }
        for (int i = 0; i < res.size(); ++i) {
            if (i) printf(" ");
            printf("%d", res[i]);
        }
        printf("\n");
    } else {
        printf("No Solution\n");
    }
    return 0;
}

關鍵點

1. 降序排列：讓大面值優先決策，回溯時從小面值開始輸出，保證字典序最小
2. 決策優先級：v[i-1][j] >= v[i-1][j-a[i]]+a[i] 時選「不選」，這對字典序最小至關重要
3. 空間優化：M ≤ 100，二維數組 10005×105 約 40MB 可接受，也可滾動數組