UVA 147 Dollars：硬幣找零完全背包計數

UVA 147 - 紐幣找零方案數：完全背包計數 DP

幣值：5,10,20,50,100,200,500,1000,2000,5000,10000（單位：分）。求金額 x (≤30000分=300元) 的找零方案數。多查詢，0.00 結束。

完全背包計數 DP

dp[v] = 湊成 v 分的方案數。初始 dp[0]=1。對每種幣值 c，正序更新：

for (int c : coins)
    for (int v=c; v<=MAXV; ++v)
        dp[v] += dp[v-c];

正序保證每種幣值可重複使用（完全背包）。方案數不考慮順序，故外層循環幣值、內層循環金額。

精度處理

輸入浮點數 x，轉整數分：n = int(x*100 + 0.5)。+0.5 解決浮點誤差（如 0.20*100=19.999...）。

代碼實現

int coins[] = {5,10,20,50,100,200,500,1000,2000,5000,10000};
unsigned long long dp[300010];
int main() {
    double x;
    while (scanf("%lf", &x), x > 0) {
        int n = int(x*100 + 0.5);
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (int c : coins)
            for (int v=c; v<=n; ++v)
                dp[v] += dp[v-c];
        printf("%6.2f%17llu\n", x, dp[n]);
    }
}

輸出格式

%6.2f：寬度 6 右對齊，兩位小數（如 " 0.20"）
%17llu：寬度 17 右對齊，無符號長長整數

優化：預處理打表

因最大金額固定（30000），可預先跑一次 DP 填滿 dp[0..30000]，查詢直接 O(1) 取值。多測試用例時極大提速。

複雜度

預處理 O(11 × 30000) = 3.3e5，查詢 O(1)。空間 O(30000)。方案數最大 dp[30000] 需 64 位無符號整數（unsigned long long）。