凑零钱问题

冷不防 2023-02-17 01:15 6阅读 0赞

题目：给你k种面值的硬币，面值分别为 c1, c2 … ck，每种硬币的数量无限，再给一个总金额 amount，问你amount 最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1

解析：假设面值c1，c2…ck是顺序排列，首先我们查看cK,最大可能 maxCout = amount /ck 个ck。那么剩下的钱amount - maxCout \*ck从c1，c2…ck-1。如果凑不齐，最大面值ck就从maxCout -1个开始。剩下的钱amount - （ maxCout - 1) \*ck从c1，c2…ck-1凑。如果最后最大面额ck个数为0，剩余钱amount 从c1，c2…ck-1凑也没有凑齐，那就是真凑不齐了。

来看下代码实现

int countCoins(vector<int> coins,int amount)
    {
        
        if ( 0 == amount)
        {
        
            return 0;
        }
        if ((coins.size() == 0) || ((coins.size() != 0) && (amount < coins.at(0))))
        {
        
            return -1;
        }
        int maxCoins = coins.at(coins.size() - 1);//最大面额
        int minMaxCoins = amount / maxCoins;// 最大面额的最多张数
        int num = minMaxCoins;
        int otherCoins = -1;
        coins.pop_back();
        //剩下的钱amount - （num) *ck从c1，c2...ck-1凑
        for ( ; num >= 0; num-- )
        {
        
            otherCoins = countCoins(coins,amount - num * maxCoins);
            if (otherCoins != -1)
            {
        
                break;
            }
        }
        //剩余钱amount 从c1，c2...ck-1凑也没有凑齐，那就是真凑不齐了。
        if (otherCoins == -1)
        {
        
            return -1;
        }
        return num + otherCoins;
    }

测试代码试一试

int main(int argc, char *argv[])
    {
        
        vector<int> coins;
        coins.push_back(2);
        coins.push_back(3);
        coins.push_back(4);
        coins.push_back(5);
        int amount = 11;
        printf("\n%d:%d ",amount,countCoins(coins,amount));
    
        amount = 1;
        printf("\n%d:%d ",amount,countCoins(coins,amount));
    
        amount = 2857;
        printf("\n%d:%d ",amount,countCoins(coins,amount));
        printf("\n");
        return 0;
    }
    /*
    运行结果：
    11:3 
    1:-1 
    2857:572   
    */