硬币找零问题——动态规划

问题阐述

给定一些面值的硬币（数量不限）和需要找零的金额，求一个找零所需硬币数最少的方案。
现实生活中因其面值的特殊性，我们往往采用贪心策略，即每次选取满足条件的面值最大的硬币。如找零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))的用法
• 在常规货币中，可以采用最大面值的贪心策略（每次加入满足条件的最大面值货币），当硬币面值不满足什么临界条件时，贪心算法不再适用？