这个问题是一样的问here.

鉴于硬币的列表，它们的值（C1，C2，C3，... CJ，...），和总和岛发现硬币的最小数量的总和，其中为i（我们可以用尽可能多的硬币中的一个类型，因为我们希望），或报告，它是不可能以这样的方式选择的硬币，他们总结至S

我只是在介绍了动态规划昨天我试图让一个code吧。

I"m just introduced to dynamic programming yesterday and I tried to make a code for it.

# 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，...} 该计划中，我增加了递归限制以避免最大递归深度超过误差。但是，这个方案提供了正确的答案只有某人并且当一个解决方案是不可能的，这并不表示。

Here, C[i] is the optimal solution for amount of money 'i'. And available coins are {c1, c2, ... , cj, ...} for the program, I've increased the recursion limit to avoid maximum recursion depth exceeded error. But, this program gives the right answer only someones and when a solution is not possible, it doesn't indicate that.

什么是错我的code和如何纠正呢？

推荐答案

这是一个伟大的算法问题，但说实话，我不认为你的实现是正确的，也可能是因为我不明白输入/输出的功能，为此，我很抱歉。照片

This is a great algorithms question, but to be honest I don't think your implementation is correct or it could be that I don't understand the input/output of your function, for that I apologize.

继承人的修改版本。

heres a modified version of your implementation.

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]

这是我在尝试解决类似的问题，但这次返回硬币的列表。我最初开始使用递归算法，它接受之和硬币的列表，其可以返回一个列表与最低限度的硬币数量或无如果可以找到这样的配置。

This is my attempt at solving a similar problem, but this time returning a list of coins. I initially started with a recursive algorithm, which accepts a sum and a list of coins, which may return either a list with the minimun number of coins or None if no such configuration could be found.

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

确定现在让我们看看我们是否能够改善它，通过使用动态规划（我只是把它缓存）。

ok now lets see if we can improve it, by using dynamic programming (I just call it caching).

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]

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

now lets run some tests.

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

授予此测试并不足够强大，你也可以做到这一点。

granted this tests aren't robust enough, you can also do this.

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但我相信它相当不可能的......

its possible that the no such combination of coins equals our random_sum but I believe its rather unlikely ...

我敢肯定有更好的实施在那里，我想强调的可读性以上的性能。 祝你好运。

Im sure there are better implementation out there, I tried to emphasize readability more than performance. good luck.

更新 在previous code有一个小错误的假设来检查分硬币并非最大，重新写有PEP8合规性和回报率的算法 [] 时，没有组合能找到，而不是无。

Updated the previous code had a minor bug its suppose to check for min coin not the max, re-wrote the algorithm with pep8 compliance and returns [] when no combination could be found instead of 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])] ])