问题阐述
给定一些面值的硬币（数量不限）和需要找零的金额，求一个找零所需硬币数最少的方案。
现实生活中因其面值的特殊性，我们往往采用贪心策略，即每次选取满足条件的面值最大的硬币。如找零16元，贪心策略是10+5+1=16，而当硬币面值为1，5，8，10时，只需两个8元硬币即可满足。
分析
用动态规划的方法，屡次从子问题的最优解中找到当前情况的最优方案。例如，找零16元，可依次查看找零16-1=15元、16-5=11元、16-8=8元、16-10=6元时需要的最少硬币数，在此基础上加一就为当前的最优方案。
数据结构
- 需要找零的金额money
- m种面值的硬币，crr[m]数组，crr[i]表示第i种面值大小
-
dp[money]：动态规划数组，dp[i]=j表示找零i元所需的最少硬币数
状态转移
初始化数组dp[m]为一个极大值
对每个大于crr[i]的金额M，取dp[M] = min(dp[M], dp[M-crr[i]]+1)
代码实现
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 205;
const int INF = 0xfffffff;
int main()
{
int m; cin>>m;
int crr[m], dp[maxn], money;
//memset(dp, INF, sizeof(dp));
memset(crr, 0, sizeof(crr));
for(int i=0;i<m;i++){
cin >> crr[i];
}
cin >> money;
dp[0]=0;
for(int i=1;i<=money;i++) dp[i]=INF; //初始化dp数组元素为一个极大整数
for(int i=1;i<=money;i++){
for(int j=0; j<m;j++){
if(i>=crr[j]) dp[i] = min(dp[i], dp[i-crr[j]]+1); //状态转移
}
}
cout << dp[money];
return 0;
}
Q
- memset(a, 0, sizeof(a))的用法
- 在常规货币中，可以采用最大面值的贪心策略（每次加入满足条件的最大面值货币），当硬币面值不满足什么临界条件时，贪心算法不再适用？
