1

コインの変更に関する質問と回答がたくさんありますが、これを見つけることができず、コインの変更の問題でさえあるのだろうかと思っています.

基本的に、私はさまざまなコインをたくさん持っていて、それぞれのコインは無限にあります。

つまり、さまざまな宗派のスタックがあるとします。各スタックは無限です。(つまり、無限の 25c コイン、無限の 2c コインなど)。

ただし、コインの各スタックの上には、下のコインよりも大きい (または等しい) 値を持つ特別なコインがあります。上のコインを使わないと下のコインにアクセスできません。

私が解決しようとしているのは、特定の合計を作るために必要なコインの最小数です。

これは解決可能な動的計画法だと思いますが、この制限を従来のソリューションに追加する方法がわかりません。

使用したらリストから特別なコインを削除して通常のコインに置き換えるかどうか疑問に思っていましたが、それがアルゴリズムを壊すかどうかを判断することはできません.

4

2 に答える 2

0

課題は状態を正しく選択することである古典的な動的計画問題のように見えます。

通常、選択したコインの合計を問題の状態として選択し、選択したコインの数を状態値として選択します。トランジションは、私たちが取ることができるすべてのコインです。25c と 5c のコインがある場合、値が Count の状態 Sum から状態Sum+25,count+1andに移動できSum+5,count+1ます。

あなたの制限のために、どの特別な（トップ）コインが取られたかについての情報で状態を増強する必要があります。したがって、コインのスタックごとにビットを追加します。次に、すべての状態から可能な遷移を定義する必要があります。それは簡単です: スタックのビットが設定されている場合、それはトップ コインが既に取得されていることを意味し、すべてのビットを同じに保ちながら、そのスタックから状態合計に非トップ コインを追加できます。それ以外の場合は、そのスタックから一番上のコインを取り、その値を州の合計に追加し、関連するビットを設定できます。

合計が 0、すべてのビットがクリア、値が 0 の状態から開始し、最小の合計からターゲットまでの状態を構築します。

最後に、ビットとのすべての可能な組み合わせを反復処理する必要があります。状態の値をターゲットの合計とそのビットの組み合わせと比較します。最小値を選択してください - それが答えです。

ソリューション コードの例:

#Available coins: (top coin value, other coins value)
stacks = [(17,8),(5,3),(11,1),(6,4)]
#Target sum
target_value = 70

states = dict()
states[(0,0)] = (0,None,None)
#DP going from sum 0 to target sum, bottom up:
for value in xrange(0, target_value):
    #For each sum, consider every possible combination of bits
    for bits in xrange(0, 2 ** len(stacks)):
        #Can we get to this sum with this bits?
        if (value,bits) in states:
            count = states[(value,bits)][0]
            #Let's take coin from each stack
            for stack in xrange(0, len(stacks)):                
                stack_bit = (1 << stack)                
                if bits & stack_bit:
                    #Top coin already used, take second
                    cost = stacks[stack][1]
                    transition = (value + cost, bits)
                else:
                    #Top coin not yet used
                    cost = stacks[stack][0]
                    transition = (value + cost, bits | stack_bit)
                #If we can get a better solution for state with sum and bits
                #update it 
                if (not (transition in states)) or states[transition][0] > count + 1:
                    #First element is coins number
                    #Second is 'backtrack reference'
                    #Third is coin value for this step
                    states[transition] = (count+1, (value,bits), cost)

min_count = target_value + 1
min_state = None
#Find the best solution over all states with sum=target_value
for bits in xrange(0, 2 ** len(stacks)):
    if (target_value,bits) in states:
        count = states[(target_value,bits)][0]
        if count < min_count:
            min_count = count
            min_state = (target_value, bits)
collected_coins = []
state = min_state
if state == None:
    print "No solution"
else:
    #Follow backtrack references to get individual coins
    while state <> (0,0):
        collected_coins.append(states[state][2])
        state = states[state][1]
    print "Solution: %s" % list(reversed(collected_coins))
于 2015-10-24T02:18:37.197 に答える