0

指定された宗派のリストの合計からコインの最小数を計算するためのこのコードがあります。例： minimum change for 69 with denomiations [25,10,5,1] : [25, 25, 10, 5, 1, 1, 1, 1]

def get_min_coin_configuration(sum=None, coins=None, cache={}):
    #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 min(coins) > sum:  # if the largest coin is greater then the sum, there's nothing we can do.
        #cache[sum] = []
        #return cache[sum]
        return []
    else:  # check for each coin, keep track of the minimun configuration, then return it.
        min_length = 0
        min_configuration = []
        for coin in coins:
            results = get_min_coin_configuration(sum - coin, coins, cache)
            if results != []:
                if min_length == 0 or (1 + len(results)) < len(min_configuration):
                    #print "min config", min_configuration
                    min_configuration = [coin] + results
                    #print "min config", min_configuration
                    min_length = len(min_configuration)
                    cache[sum] = min_configuration
        return cache[sum]
if __name__ == "__main__":
    print "minimum change for 69 with denomiations [25,10,5,1] by recursive : ",get_min_coin_configuration(69,[25,10,5,1])
    print "*"*45
    print "minimum change for 7 with denomiations [4,3,1] by recursive : ",get_min_coin_configuration(7,[4,3,1])

メインの print ステートメントのいずれかをコメントアウトすると、プログラムは正常に動作するようです。両方の関数呼び出しがあると、間違って印刷されます。メインのいずれかの print ステートメントをコメントアウトすると、最小コインが正しく出力されることがわかります。

minimum change for 69 with denomiations [25,10,5,1] by recursive :  [25, 25, 10, 5, 1, 1, 1, 1]
*********************************************
minimum change for 7 with denomiations [4,3,1] by recursive :  [5, 1, 1]
4

1 に答える 1

1 
if __name__ == "__main__":
    cache_denom_set1 = {}
    cache_denom_set2 = {}
    print "minimum change for 69 with denomiations [25,10,5,1] by recursive : ",get_min_coin_configuration(69,[25,10,5,1],cache_denom_set1)
    print "*"*45
    print "minimum change for 7 with denomiations [4,3,1] by recursive : ",get_min_coin_configuration(7,[4,3,1],cache_denom_set2)

額面セットごとに個別のキャッシュを渡す

問題は、キャッシュが 7 を 5,1,1 に変更する方法を既に知っているため、それを返すだけであるということです...キャッシュは、5 が金種セットに含まれなくなったことを認識していません...

辞書はリストのように変更可能です...これは問題を示すはずです

def dict_fn(cache={}):
    cache[len(cache.keys())] = 1
    print cache

dict_fn()
dict_fn()
于 2013-11-13T19:19:30.040 に答える