問(wèn)題闡述

給定一些面值的硬幣（數(shù)量不限）和需要找零的金額，求一個(gè)找零所需硬幣數(shù)最少的方案。
現(xiàn)實(shí)生活中因其面值的特殊性，我們往往采用貪心策略，即每次選取滿足條件的面值最大的硬幣。如找零16元，貪心策略是10+5+1=16，而當(dāng)硬幣面值為1，5，8，10時(shí)，只需兩個(gè)8元硬幣即可滿足。

分析

用動(dòng)態(tài)規(guī)劃的方法，屢次從子問(wèn)題的最優(yōu)解中找到當(dāng)前情況的最優(yōu)方案。例如，找零16元，可依次查看找零16-1=15元、16-5=11元、16-8=8元、16-10=6元時(shí)需要的最少硬幣數(shù)，在此基礎(chǔ)上加一就為當(dāng)前的最優(yōu)方案。

數(shù)據(jù)結(jié)構(gòu)

• 需要找零的金額money
• m種面值的硬幣，crr[m]數(shù)組，crr[i]表示第i種面值大小
• dp[money]：動(dòng)態(tài)規(guī)劃數(shù)組，dp[i]=j表示找零i元所需的最少硬幣數(shù)
  狀態(tài)轉(zhuǎn)移
  初始化數(shù)組dp[m]為一個(gè)極大值
  對(duì)每個(gè)大于crr[i]的金額M，取dp[M] = min(dp[M], dp[M-crr[i]]+1)

代碼實(shí)現(xiàn)

#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數(shù)組元素為一個(gè)極大整數(shù)
    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);  //狀態(tài)轉(zhuǎn)移
        }
    }
    cout << dp[money];
    return 0;
}

Q

• memset(a, 0, sizeof(a))的用法
• 在常規(guī)貨幣中，可以采用最大面值的貪心策略（每次加入滿足條件的最大面值貨幣），當(dāng)硬幣面值不滿足什么臨界條件時(shí)，貪心算法不再適用？