硬币兑换的复杂性有限

Question

如果每枚硬币的数量是无限的，那么复杂性是O（n*m），其中n是总变化，m是硬币类型的数量。现在，当每种类型的硬币都受到限制时，我们必须考虑剩余的硬币。我设法使它与O（n*m2）的复杂性使用另一个大小的n，所以我可以跟踪每个类型的剩余硬币。有没有一种方法可以让复杂性变得更好？编辑：问题是计算进行精确给定更改所需的最少硬币数量以及我们使用每种硬币类型的次数

Answer 1

下面是Python中O（nm）解决方案的实现。

如果定义C（C，k）=1x^cx^（2c）。。。x^（kc），然后程序计算多项式乘积（C（C[i]，k[i]），i=1…ncoins）的第一个n1系数。此多项式的j第个系数是对j进行更改的方法数。

当所有的ks不受限制时，该多项式乘积易于计算（例如，请参见：https://stackoverflow.com/a/20743780/1400793)。当受到限制时，需要能够有效地计算k项的运行和，这是在程序中使用rs数组完成的。

# cs is a list of pairs (c, k) where there's k
# coins of value c.
def limited_coins(cs, n):
    r = [1] + [0] * n
    for c, k in cs:
        # rs[i] will contain the sum r[i] + r[i-c] + r[i-2c] + ...
        rs = r[:]
        for i in xrange(c, n+1):
            rs[i] += rs[i-c]
            # This line effectively performs:
            # r'[i] = sum(r[i-j*c] for j=0...k)
            # but using rs[] so that the computation is O(1)
            # and in place.
            r[i] += rs[i-c] - (0 if i<c*(k+1) else rs[i-c*(k+1)])
    return r[n]

for n in xrange(50):
    print n, limited_coins([(1, 3), (2, 2), (5, 3), (10, 2)], n)

Answer 2

不需要额外的循环。您需要：

• 递归深度最多为m（硬币数量）级别，每个递归级别处理一个特定硬币

下面是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}
]

如注释中所述，上述算法返回其找到的第一个解决方案。如果有一个要求，即当存在多个解决方案时，单个硬币的数量必须最小化，那么您不能在循环的一半返回，而是必须保留迄今为止找到的“最佳”解决方案。

以下是为实现此目的而修改的代码：

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}
]