3

这个问题和这里问的一样。

给定一个硬币列表,它们的值 (c1, c2, c3, ... cj, ...) 和总和 i。找到总和为 i 的最小硬币数量(我们可以使用任意数量的一种类型的硬币),或者报告不可能以总和为 S 的方式选择硬币。

我昨天刚接触到动态编程,我试图为它编写代码。

# Optimal substructure: C[i] = 1 + min_j(C[i-cj])
cdict = {}
def C(i, coins):

    if i <= 0:
        return 0

    if i in cdict:
        return cdict[i]
    else:
        answer = 1 + min([C(i - cj, coins) for cj in coins])
        cdict[i] = answer
        return answer

这里,C[i] 是金额“i”的最优解。并且可用的硬币是程序的 {c1, c2, ... , cj, ...},我增加了递归限制以避免最大递归深度超出错误。但是,这个程序只给出了正确的答案,当解决方案不可能时,它并不表明这一点。

我的代码有什么问题以及如何纠正它?

4

5 回答 5

5

这是一个很好的算法问题,但老实说,我认为您的实现不正确,或者可能是我不理解您的函数的输入/输出,对此我深表歉意。

这是您的实施的修改版本。

def C(i, coins, cdict = None):
    if cdict == None:
        cdict = {}
    if i <= 0:
        cdict[i] = 0
        return cdict[i]
    elif i in cdict:
        return cdict[i]
    elif i in coins:
        cdict[i] = 1
        return cdict[i]
    else:
        min = 0
        for cj in coins:
            result = C(i - cj, coins)
            if result != 0:
                if min == 0 or (result + 1) < min:
                    min = 1 + result
        cdict[i] = min
        return cdict[i]

这是我解决类似问题的尝试,但这次返回了一个硬币列表。我最初从一个递归算法开始,它接受一个总和和一个硬币列表,如果找不到这样的配置,它可能会返回一个包含最少硬币数量的列表或 None 。

def get_min_coin_configuration(sum = None, coins = None):
if sum in coins: # if sum in coins, nothing to do but return.
    return [sum]
elif max(coins) > sum: # if the largest coin is greater then the sum, there's nothing we can do.
    return None
else: # check for each coin, keep track of the minimun configuration, then return it.
    min_length = None
    min_configuration = None
    for coin in coins:
        results = get_min_coin_configuration(sum = sum - coin, coins = coins)
        if results != None:
            if min_length == None or (1 + len(results)) < len(min_configuration):
                min_configuration = [coin] + results
                min_length = len(min_configuration)
    return min_configuration

好的,现在让我们看看我们是否可以通过使用动态编程(我称之为缓存)来改进它。

def get_min_coin_configuration(sum = None, coins = None, cache = None):
if cache == None: # this is quite crucial if its in the definition its presistent ...
    cache = {}
if sum in cache:
    return cache[sum]
elif sum in coins: # if sum in coins, nothing to do but return.
    cache[sum] = [sum]
    return cache[sum]
elif max(coins) > sum: # if the largest coin is greater then the sum, there's nothing we can do.
    cache[sum] = None
    return cache[sum]
else: # check for each coin, keep track of the minimun configuration, then return it.
    min_length = None
    min_configuration = None
    for coin in coins:
        results = get_min_coin_configuration(sum = sum - coin, coins = coins, cache = cache)
        if results != None:
            if min_length == None or (1 + len(results)) < len(min_configuration):
                min_configuration = [coin] + results
                min_length = len(min_configuration)
    cache[sum] = min_configuration
    return cache[sum]

现在让我们运行一些测试。

assert all([ get_min_coin_configuration(**test[0]) == test[1] for test in
[({'sum':25,  'coins':[1, 5, 10]}, [5, 10, 10]),
 ({'sum':153, 'coins':[1, 5, 10, 50]}, [1, 1, 1, 50, 50, 50]),
 ({'sum':100, 'coins':[1, 5, 10, 25]}, [25, 25, 25, 25]),
 ({'sum':123, 'coins':[5, 10, 25]}, None),
 ({'sum':100, 'coins':[1,5,25,100]}, [100])] ])

如果这个测试不够健壮,你也可以这样做。

import random
random_sum = random.randint(10**3, 10**4)
result = get_min_coin_configuration(sum = random_sum, coins = random.sample(range(10**3), 200))
assert sum(result) == random_sum

有可能没有这样的硬币组合等于我们的 random_sum,但我相信它不太可能......

我确信那里有更好的实现,我试图强调可读性而不是性能。祝你好运。

更新 了之前的代码有一个小错误,它假设检查 min coin 而不是 max,重新编写了符合 pep8 的算法,并[]在找不到组合而不是None.

def get_min_coin_configuration(total_sum, coins, cache=None):  # shadowing python built-ins is frowned upon.
    # assert(all(c > 0 for c in coins)) Assuming all coins are > 0
    if cache is None:  # initialize cache.
        cache = {}
    if total_sum in cache:  # check cache, for previously discovered solution.
        return cache[total_sum]
    elif total_sum in coins:  # check if total_sum is one of the coins.
        cache[total_sum] = [total_sum]
        return [total_sum]
    elif min(coins) > total_sum:  # check feasibility, if min(coins) > total_sum
        cache[total_sum] = []     # no combination of coins will yield solution as per our assumption (all +).
        return []
    else:
        min_configuration = []  # default solution if none found.
        for coin in coins:  # iterate over all coins, check which one will yield the smallest combination.
            results = get_min_coin_configuration(total_sum - coin, coins, cache=cache)  # recursively search.
            if results and (not min_configuration or (1 + len(results)) < len(min_configuration)):  # check if better.
                min_configuration = [coin] + results
        cache[total_sum] = min_configuration  # save this solution, for future calculations.
    return cache[total_sum]



assert all([ get_min_coin_configuration(**test[0]) == test[1] for test in
             [({'total_sum':25,  'coins':[1, 5, 10]}, [5, 10, 10]),
              ({'total_sum':153, 'coins':[1, 5, 10, 50]}, [1, 1, 1, 50, 50, 50]),
              ({'total_sum':100, 'coins':[1, 5, 10, 25]}, [25, 25, 25, 25]),
              ({'total_sum':123, 'coins':[5, 10, 25]}, []),
              ({'total_sum':100, 'coins':[1,5,25,100]}, [100])] ])
于 2012-06-11T04:40:28.017 回答
1

就像评论说的那样,你需要在 when 时返回一个足够大的值i < 0,这样它就不会被你min这样选择:

cdict = {}
def C(i, coins):

    if i == 0:
        return 0

   if i < 0:
        return 1e100    # Return infinity in ideally

    if i in cdict:
        return cdict[i]
    else:
        answer = 1 + min([C(i - cj, coins) for cj in coins])
        cdict[i] = answer
    return answer

现在只要函数返回 1e100,就意味着无法解决。

例如:

$ python2 coins.py 13555 1 5 9
1507  coins
$ python2 coins.py 139 1 5 9
19  coins
$ python2 coins.py 139  5 9
19  coins
$ python2 coins.py 13977  5 9
1553  coins
$ python2 coins.py 13977   9
1553  coins
$ python2 coins.py 139772   9
1e+100  coins

用法:

python2 coins.py <amount> <coin1> <coin2> ...
于 2012-06-11T04:37:16.130 回答
1

这是一个有趣的方法。有点hack,但这就是为什么它很有趣。

    import math

    def find_change(coins, value):
        coins = sorted(coins, reverse=True)
        coin_dict = {}
        for c in coins:
            if value % c == 0:
                coin_dict[c] = value / c
                return coin_dict
            else:
                coin_dict[c] = math.trunc(value/ float(c))
                value -= (c * coin_dict[c])

    coins = [1, 5, 10, 25]
    answer = find_change(coins, 69)
    print answer
    [OUT]: {25: 2, 10: 1, 5: 1, 1: 4}

下面是带有边缘保护的注释的相同解决方案

    import math
    def find_change(coins, value):
        '''
        :param coins: List of the value of each coin [25, 10, 5, 1]
        :param value: the value you want to find the change for ie; 69 cents
        :return: a change dictionary where the key is the coin, and the value is how many times it is used in finding the minimum change
        '''
        change_dict = {}  # CREATE OUR CHANGE DICT, THIS IS A DICT OF THE COINS WE ARE RETURNING, A COIN PURSE
        coins = sorted(coins, reverse=True)  # SORT COINS SO WE START LOOP WITH BIGGEST COIN VALUE
        for c in coins:
            for d in coins:     # THIS LOOP WAS ADDED BY A SMART STUDENT:  IE IN THE CASE OF IF THERE IS A 7cent COIN AND YOU ARE LOOKING FOR CHANGE FOR 14 CENTS, WITHOUT THIS D FOR LOOP IT WILL RETURN 10: 1, 1: 4
                if (d != 1) & (value % d == 0):
                    change_dict[d] = value / d
                    return change_dict
            if value % c == 0:      # IF THE VALUE DIVIDED BY THE COIN HAS NO REMAINDER,  # ie, if there is no remainder, all the neccessary change has been given  # PLACE THE NUMBER OF TIMES THAT COIN IS USED IN THE change_dict  # YOU ARE FINISHED NOW RETURN THE change_dict
                change_dict[c] = value / c
                return change_dict
            else:
                change_dict[c] = math.trunc(value/ float(c))        # PLACE THAT NUMBER INTO OUR coin_dict  # DIVIDE THE VALUE BY THE COIN, THEN GET JUST THE WHOLE NUMBER  # IE 69 / 25.0 = 2.76  # math.trunc(2.76) == 2    # AND THAT IS HOW MANY TIMES IT WILL EVENLY GO INTO THE VALUE,
                amount = (c * change_dict[c])  # NOW TAKE THE NUMBER OF COINS YOU HAVE IN YOUR  UPDATE THE VALUE BY SUBTRACTING THE c * TIME NUMBER OF TIMES IT WAS USED    # AMOUNT IS HOW MUCH CHANGE HAS BEEN PUT INTO THE CHANGE DICT ON THIS LOOP  # FOR THE CASE OF 69, YOU GIVE 2 25CENT COINS, SO 2 * 25 = 50, 19 = 69 - 50
                value = value - amount              # NOW, UPDATE YOUR VALUE, SO THE NEXT TIME IT GOES INTO THIS LOOP, IT WILL BE LOOKING FOR THE MIN CHANGE FOR 19 CENTS...

    coins = [1, 5, 10, 25]
    answer = find_change(coins, 69)
    print answer
    [OUT]: {25: 2, 10: 1, 5: 1, 1: 4}
    edge_case_coins = [1, 7, 10, 25]
    edge_case_answer = find_change(coins, 14)
    print edge_case_answer
    [OUT]: {7: 2}
于 2014-10-02T18:01:59.573 回答
0

这是用于找零的算法的递归且非常V低效的实现,其中是硬币列表和C目标金额:

def min_change(V, C):
    def min_coins(i, aC):
        if aC == 0:
            return 0
        elif i == -1 or aC < 0:
            return float('inf')
        else:
            return min(min_coins(i-1, aC), 1 + min_coins(i, aC-V[i]))
    return min_coins(len(V)-1, C)

这是同一算法的动态编程版本:

def min_change(V, C):
    m, n = len(V)+1, C+1
    table = [[0] * n for x in xrange(m)]
    for j in xrange(1, n):
        table[0][j] = float('inf')
    for i in xrange(1, m):
        for j in xrange(1, n):
            aC = table[i][j - V[i-1]] if j - V[i-1] >= 0 else float('inf')
            table[i][j] = min(table[i-1][j], 1 + aC)
    return table[m-1][n-1]
于 2012-06-11T04:43:39.070 回答
0

这是一个使用 while 循环的方法。该算法非常简单。您首先使用最大的硬币来支付这笔钱。如果你知道你会过去,你会切换到下一个较小的硬币并重复直到钱为 0。这段代码的优点是,虽然最坏情况的运行时间更高(我认为它是 m*n(m 是列表的大小,而n 是 while 中的迭代),代码要简单得多。

我假设没有价值 0 的硬币,总是有价值 1 的硬币。当没有价值 1 时,该函数将给出价格下最佳硬币数量的答案。

def find_change(coins, money):
    coins = sorted(coins, reverse=True)
    coincount = 0

    for coin in coins:
        while money >= coin:
            money = money - coin
            coincount += 1

    return coincount

我试图想到一个不起作用的极端情况(它会溢出任何具有 0 值硬币的列表)但想不出一个。

于 2014-10-03T03:09:20.600 回答