程序员的算法趣题Q05: 硬币兑换

1. 问题描述

本题来自《程序员的算法趣题》中的第5题。

公交车上的零钱兑换机可以将纸币兑换成10日元、50日元、100日元和500日元的硬币，且每种硬币的数量都足够多。因为兑换出太多的硬币不太方便，只允许机器兑换成最多15枚硬币。比如说1000日元的纸币就不能对换成100枚10日元的硬币。

求兑换1000日元纸币会出现多少种不同组合？注意不计硬币兑出的先后顺序（即可以认为硬币是一起出来的）。

2. 递推表达式

这道题目可以表达为如下数学方程的形式：

这是一道线性规划（Linear Programming）问题。

More generally, 令所需要兑换的纸币记为money，可用的硬币以数组形式（降序排列）表示为coins，最多允许的硬币数为maxNum。记f(money, coins, maxNum)表示符合题设要求的组合数。

首先考虑最大面值的硬币coins[0]（假定coins中按降序排列）的使用。很显然，coins[0]最少可以用0枚（即不同），最多可以用 枚，据此可以把问题分解为若干个更“小”的子问题来求解。由此可以得到以下递推关系式：

Baseline cases或者说边界条件如下：

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Mon Aug 23 08:35:32 2021

@author: chenxy
"""

import sys
import time
import random
from math import gcd, sqrt, ceil
from   typing import List
# from   queue import Queue

class Solution:

    def coinChange(self, money:int, coins:List, maxNum: int)->int:
        """
        :money:  The money value to be changed into coins
        :coins:  Candiate coins in decreasing value order
        :    
        :ret:    The number of the solutions
        """
        # print('money={0}, coins={1}, maxNum={2}'.format(money,coins,maxNum))
        # Boundary cases
        if money == 0:
            return 1
        
        if len(coins) == 0:
            return 0
        
        # If money is less than the smallest coin, then the change is unsuccessful
        if money < coins[-1]:
            return 0
        
        # Cannot be changed into no larger than maxNum coins
        if ceil(money/coins[0]) > maxNum:
            return 0
        
        nums = 0
        for k in range(money//coins[0]+1):
            nums += self.coinChange(money-k*coins[0], coins[1:], maxNum-k)
            
        return nums

if __name__ == '__main__':        
    
    sln = Solution()

    money = 1000
    coins = [500,100,50,10] # In decreasing value order
    maxNum= 15
    tStart = time.time()
    nums = sln.coinChange(money, coins, maxNum)
    tCost = time.time() - tStart
    print('maney = {0}, coins = {1}, nums = {2}, tCost = {3}(sec)'.format(money,coins,nums,tCost))      

测试运行结果如下：

money = 1000, coins = [500, 100, 50, 10], nums = 20, tCost = 0.0(sec)

但是以上题解中只给出了硬币兑换方案的种类数，并没有给出具体的兑换方案。应该如何修改程序给出具体的每种兑换方案呢？