零钱复杂度有限的硬币找零 [英] Coin change with limited coins complexity

问题描述

如果每种硬币的数量不受限制，则复杂度为 O(n * m)，其中 n 是总找零，而 m 是硬币类型的数量.现在，当每种类型的硬币受到限制时，我们必须考虑剩余的硬币.我设法使其复杂度为 O(n * m 2 )，使用另一个大小为 n 的它，因此我可以跟踪其余的每种类型的硬币.有没有什么技巧可以使复杂性更好?问题是要计算出进行精确给定的更改所需的最少硬币数量，以及我们使用每种硬币类型的次数

If there is an unlimited number of every coin then the complexity is O(n*m) where is n is the total change and m is the number of coin types. Now when the coins for every type are limited then we have to take into account the remaining coins. I managed to make it work with a complexity of O(n*m2) using another for of size n so I can track the remaining coins for each type. Is there a way-trick to make the complexity better? EDIT : The problem is to compute the least ammount of coins required to make the exact given change and the number of times that we used each coin type

推荐答案

不需要额外的循环.您需要:

There is no need for an extra loop. You need to:

• 深度最多为 m (硬币数量)级别的递归，每个递归级别处理一个特定的硬币.
• 在每个递归级别上最多循环 n 次，以便确定您将要给定硬币的数量.

• recurse with a depth of at most m (number of coins) levels, dealing with one specific coin per recursion level.
• Loop at most n times at each recursion level in order to decide how many you will take of a given coin.

这是代码在Python 3中的外观:

Here is how the code would look in Python 3:

def getChange(coins, amount, coinIndex = 0):
    if amount == 0:
        return [] # success
    if coinIndex >= len(coins):
        return None # failure
    coin = coins[coinIndex]
    coinIndex += 1
    # Start by taking as many as possible from this coin
    canTake = min(amount // coin["value"], coin["count"])
    # Reduce the number taken from this coin until success
    for count in range(canTake, -1, -1): # count will go down to zero
        # Recurse to decide how many to take from the next coins
        change = getChange(coins, amount - coin["value"] * count, coinIndex)
        if change != None: # We had success
            if count: # Register this number for this coin:
                return change + [{ "value": coin["value"], "count": count }]
            return change


# Example data and call:
coins = [
    { "value": 20, "count":  2 },   
    { "value": 10, "count":  2 },
    { "value":  5, "count":  3 },
    { "value":  2, "count":  2 },
    { "value":  1, "count": 10 }
]

result = getChange(coins, 84)
print(result)

给定示例的输出:

[
    {'value': 1, 'count': 5},
    {'value': 2, 'count': 2},
    {'value': 5, 'count': 3},
    {'value': 10, 'count': 2},
    {'value': 20, 'count': 2}
]

最小化使用的硬币数量

如评论中所述，以上算法返回其找到的第一个解决方案.如果有多种解决方案时要求将单个硬币的数量减少到最低限度，则您不能半途返回，而必须保留迄今为止找到的最佳"解决方案.

Minimising the number of coins used

As stated in comments, the above algorithm returns the first solution it finds. If there is a requirement that the number of individual coins must be minimised when there are multiple solutions, then you cannot return halfway a loop, but must retain the "best" solution found so far.

以下是修改代码以实现该目标:

Here is the modified code to achieve that:

def getchange(coins, amount):
    minCount = None

    def recurse(amount, coinIndex, coinCount):
        nonlocal minCount
        if amount == 0:
            if minCount == None or coinCount < minCount:
                minCount = coinCount
                return [] # success
            return None # not optimal
        if coinIndex >= len(coins):
            return None # failure
        bestChange = None
        coin = coins[coinIndex]
        # Start by taking as many as possible from this coin
        cantake = min(amount // coin["value"], coin["count"])
        # Reduce the number taken from this coin until 0
        for count in range(cantake, -1, -1):
            # Recurse, taking out this coin as a possible choice
            change = recurse(amount - coin["value"] * count, coinIndex + 1, 
                                                             coinCount + count)
            # Do we have a solution that is better than the best so far?
            if change != None: 
                if count: # Does it involve this coin?
                    change.append({ "value": coin["value"], "count": count })
                bestChange = change # register this as the best so far
        return bestChange

    return recurse(amount, 0, 0)

coins = [{ "value": 10, "count":  2 },
         { "value":  8, "count":  2 },
         { "value":  3, "count": 10 }]

result = getchange(coins, 26)
print(result)

输出:

[
    {'value': 8, 'count': 2},
    {'value': 10, 'count': 1}
]

这篇关于零钱复杂度有限的硬币找零的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！