Python動的プログラミング

Question

でお金を変えるここにお金の問題を変えるための2つのプログラムがあります。最初のものはすべての組み合わせを取得する唯一の再帰プログラムで、もう1つは動的プログラミングを使用しています。しかし、私が第二のものに取り組んでいるとき、私は困ってしまいます。最初のものより速いと思われますが、私のプログラムはそれを実行するためにずっと動いています。ダイナミックプログラミングを使用していると確信していますが、何が問題なのか分かりません。

注：合計は、変更される予定の金額です。単位は、異なる値のリストであり、ステップの値を格納する辞書です。

まず：

def changeMoney(total, units): 
    if (total == 0): 
     return [{}] 
    elif (total < 0): 
     return [] 
    else: 
     n = len(units) 
     ret = [] 
     for i in range(0,n): 
      sols = changeMoney(total-units[i],units[i:n]) 
      for sol in sols: 
       if (units[i] in sol): 
        sol[units[i]] += 1 
       else: 
        sol[units[i]] = 1 
      ret.append(sol) 
     return ret 
print(dpChangeMoney(300,[100,50,20,10,5,2,1],{})) 

第二：

import copy 
def dpChangeMoney(total, units, stored): 
    key = ".".join(map(str,[total] + units)) 
    if key in stored: 
     return stored[key] 
    else: 
     if (total == 0): 
      return [{}] 
     elif (total < 0): 
      return [] 
     else: 
      n = len(units) 
      for i in range(0,n): 
       sols = copy.deepcopy(dpChangeMoney(total- 
units[i],units[i:n], stored)) 
       for sol in sols: 
        if (units[i] in sol): 
         sol[units[i]] += 1 
        else: 
         sol[units[i]] = 1 
        if key in stored: 
         if sol not in stored[key]: 
          stored[key] += [sol] 
        else: 
         stored[key] = [sol] 
     return stored[key] 
print(dpChangeMoney(300,[100,50,20,10,5,2,1],{})) 

Answer 1

はここでこれを行うにははるかに高速な方法です：次のように呼び出された場合

def dpChangeMoney(total, units, stored, min_ix=0): 
    if total < 0: 
     return [] 

    if total == 0: 
     return [{}] 

    if min_ix == len(units): 
     return [] 

    key = (total, min_ix) 
    if key in stored: 
     return stored[key] 

    sol_list = [] 
    u = units[min_ix] 
    for c in range(total // u + 1): 
     sols = dpChangeMoney(total - c*u, units, stored, min_ix + 1) 
     for sol in sols: 
      if c > 0: 
       sol2 = sol.copy() 
       sol2[u] = c 
      else: 
       sol2 = sol 
      sol_list.append(sol2) 

    stored[key] = sol_list 
    return sol_list 

、それは指定された場合の解の数を出力します。

print(len(dpChangeMoney(300, [100,50,20,10,5,2,1], {}))) 

結果は次のとおりです。

466800 

私のシステムでは、これは2分の1以下で動作しました。 （もちろん、あなたが実際のソリューションを印刷することもできますが、たくさんあります！）

を10の合計の実際のソリューションを参照するには、次の

print(dpChangeMoney(10, [100,50,20,10,5,2,1], {})) 

結果は次のとおりです。

[{1: 10}, {1: 8, 2: 1}, {1: 6, 2: 2}, {1: 4, 2: 3}, {1: 2, 2: 4}, {2: 5}, {1: 5, 5: 1}, {1: 3, 2: 1, 5: 1}, {1: 1, 2: 2, 5: 1}, {5: 2}, {10: 1}] 

Answer 2

私はちょうど私のアルゴリズムで問題となっているかを把握。私は期日後にはるかに高速なアルゴリズムを更新します。あなたの提案と手順をお寄せいただきありがとうございます。 E