UVa 147 Dollars

题目描述

新西兰货币包含以下面值的纸币和硬币：

• 纸币：$100、$50、$20、$10、$5
• 硬币：$2、$1、50c、20c、10c、5c

题目要求：给定一个金额（以美元为单位，保证是5c的整数倍），计算该金额可以由这些面值组合成的不同方式数量。顺序不同不算不同方式。例如20c有以下四种组合方式：

1. 1 × 20c
2. 2 × 10c
3. 10c + 2 × 5c
4. 4 × 5c

输入格式

• 输入包含多行，每行一个实数，表示金额，不超过$300.00。
• 每个金额保证是5c的整数倍。
• 输入以一行0.00结束。

输出格式

• 每个金额输出一行，包含金额（保留两位小数，右对齐，宽度为6 66）和组合方式数量（右对齐，宽度为17 1717）。

示例输入

0.20 2.00 0.00

示例输出

0.20 4 2.00 293

问题分析

这是一个典型的完全背包计数问题。我们需要计算用给定面值的硬币组成目标金额的不同组合数，且不考虑顺序。

为了方便计算，我们可以将金额统一转换为分（cents \texttt{cents}cents）为单位。因为所有面值都是5c的整数倍，因此可以将金额除以5 55来简化问题规模。

转换面值

转换后的面值（以5c为单位）：

这样，问题转化为：用上述11 1111种面值（单位是5c），组成目标金额n nn（已除以5 55）的不同方式数。

动态规划设计

设d p [ i ] dp[i]dp[i]表示组成金额i ii的组合方式数量。
初始状态：d p [ 0 ] = 1 dp[0] = 1dp[0]=1（什么也不取算一种方式）。

状态转移方程：
对于每种面值c cc，遍历j jj从c cc到最大金额：
d p [ j ] + = d p [ j − c ] dp[j] += dp[j - c]dp[j]+=dp[j−c]

该方程表示：若我们使用一个面值为c cc的硬币，则剩余金额为j − c j-cj−c，其组合数为d p [ j − c ] dp[j-c]dp[j−c]，累加到当前d p [ j ] dp[j]dp[j]中。

算法步骤

1. 将金额转换为整数（分），再除以5 55得到目标值t a r g e t targettarget。
2. 使用动态规划预处理出所有可能金额（最大为300.00 300.00300.00，即6000 60006000个5c单位）的组合数。
3. 对每个输入金额，直接查表输出。

代码实现

// Dollars// UVa ID: 147// Verdict: Accepted// Submission Date: 2016-01-22// UVa Run Time: 0.012s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net//// PDF 格式的试题描述和 UVa 网页上的试题描述有出入，主要是上限提高到 300 美元。输出格式亦有改变。#include<bits/stdc++.h>usingnamespacestd;longlongintcache[6001]={0};voidinitialize(){// 面值以 5c 为单位intcoins[11]={1,2,4,10,20,40,100,200,400,1000,2000};cache[0]=1;for(inti=0;i<11;i++)for(intj=1;j<6001;j++)if(j-coins[i]>=0)cache[j]+=cache[j-coins[i]];}intmain(intargc,char*argv[]){initialize();string line;while(cin>>line){string backup=line;line.erase(line.find('.'),1);// 去掉小数点istringstreamiss(line);intmoney;// 单位：分iss>>money;if(money==0)break;// 输出格式：金额右对齐宽度6，组合数右对齐宽度17cout<<fixed<<setprecision(2)<<setw(6)<<right<<backup;cout<<setw(17)<<right<<cache[money/5]<<endl;}return0;}

复杂度分析

• 预处理：O ( 11 × 6000 ) ≈ 66000 O(11 \times 6000) \approx 66000O(11×6000)≈66000次操作，可忽略不计。
• 查询：O ( 1 ) O(1)O(1)。
• 空间复杂度：O ( 6000 ) O(6000)O(6000)。

总结

本题是完全背包计数问题的典型应用，通过金额单位归一化（除以5c）简化了计算，利用动态规划预处理所有可能金额的组合数，实现了高效查询。注意输入金额需要正确处理为整数形式，并满足输出格式要求。