博客

问题描述：假设有 1 元，3 元，5 元的硬币若干（无限），现在需要凑出 11 元，问如何组合才能使硬币的数量最少？

解题思路:

1、动态规划

假设总价值为i，先假设一个函数d(i)来表示需要凑出i的总价值需要的最少硬币数量。

当i=0时，我们不需要拼凑硬币，因为总价值为0

当i=1时，因为有1元我们需要1个1元，所以d(1)=1。

当i=2时，因为没有2元，所以我们需要2个1元，d(2)=2.

当i=3时，因为有3元，所以我们需要1个3元就好了，d(3)=1.

….

可以看出，除了第一步以外，往后的结果都建立在它之前得到的某一步的最优解上再加上1个硬币得出。比如d(1)=d(0)+1,d(2)=d(1)+1,d(3)=d(0)+1.

所以d(i) = d(j)+1 j < i

(1)假设最后加上的是 1 元硬币，那 d(i) = d(j) + 1 = d(i – 1) + 1。

(2)假设最后加上的是 3 元硬币，那 d(i) = d(j) + 1 = d(i – 3) + 1。

(3)假设最后加上的是 5 元硬币，那 d(i) = d(j) + 1 = d(i – 5) + 1。

需要凑18元时，我们首先找18-1=17，18-3=15，18-5,=13；再找17-1……。这样递归解决子问题

//money需要凑的钱  
//coin可用的硬币  
//硬币种类  
void FindMin(int money,int *coin, int n,int *&Num,int *&Values)
{
    Num[0] = 0;//当所凑的钱为0时，就不用凑了
    Values[0] = 0;
    for(int i=1;i<=money;i++)//要凑的钱 1....11
    {
        int minNum = 9999;//凑总价值为i的钱所需的最少硬币数，先把它初始化成一个很大的值。
        int useMoney = 0;

        for(int j=0;j<n;j++)//面值的种类 1，3，5
        {
            if(i >= coin[j])//需要凑的前大于当前面值j
            {
                int tmp = Num[i-coin[j]]+1;
                if(tmp < minNum)//更新
                {
                    minNum = Num[i-coin[j]]+1;
                    useMoney = coin[j];//最后一次添加进去的面值
                }
            }
        }
        Num[i] = minNum;
        Values[i] = useMoney;
    }
}

void printCoin(int money,int *Num,int *Values)
{
    if(Values[money] == 0)
        cout<<"没有合适的面值"<<endl;
    else
    {
        cout<<"最少需要硬币个数为:"<<Num[money]<<endl;
        cout<<"所需面值为:";
        while(money > 0)
        {
            cout<<Values[money]<<",";
            money -= Values[money];
        }
    }
}

int main()  
{  
    int money=10;  
    int coin[]={2,3,5};  

    int *num = new int[money+1]; //记录从1...money最少需要的硬币个数
    int *value = new int[money+1];//最后加入硬币，方便后面输出是哪几个硬币

    FindMin(money,coin,3,num,value);  
    printCoin(money,num,value);

    delete[]num;
    delete[]value;

    return 0;
}  

2、贪心算法

可以用每次选取可用的最大面值硬币的方法来解决。比如11，就可以是5,5,1。假如有n种面值的硬币，只要按照面值从大到小算出每种面值需要多少张，就可以解决。这种思路的时间复杂度是O(n)。

但是对于硬币的面值为{2,3,5}的时候，用该算法得到的结果是5，5。贪心算法是有局限的，对于有些条件，是无法产生正确的解的。

int MinCoin(int *arr,int n,int money)
{
    int sum = 0;
    int need = 0;

    for(int i=n-1;i>=0;i--) //从最大面值往前算
    {
        need = money / arr[i];
        printf("需要%d元的硬币%d个\n",arr[i],need);
        sum += need;
        if(money%arr[i] > 0)
            money -= need*arr[i];
        else
            money = 0;
    }
    return sum;
}
int main()
{
    int money = 11;
    int coin[] = {1,3,5};
    int n = sizeof(coin)/sizeof(coin[0]);

    int num = MinCoin(coin,n,money);
    printf("%d元最少需要%d个硬币\n",money,num);
}