5

以下のネストされたループを単純化する方法があるかどうか疑問に思っています。難しいのは、各ループのイテレータが前のループのイテレータに依存していることです。コードは次のとおりです。

# Find the number of combinations summing to 200 using the given list of coin

coin=[200,100,50,20,10,5,2,1]

total=[200,0,0,0,0,0,0,0]
# total[j] is the remaining sum after using the first (j-1) types of coin
# as specified by i below

count=0
# count the number of combinations

for i in range(int(total[0]/coin[0])+1):
    total[1]=total[0]-i*coin[0]
    for i in range(int(total[1]/coin[1])+1):
      total[2]=total[1]-i*coin[1]
      for i in range(int(total[2]/coin[2])+1):
          total[3]=total[2]-i*coin[2]
          for i in range(int(total[3]/coin[3])+1):
              total[4]=total[3]-i*coin[3]
              for i in range(int(total[4]/coin[4])+1):
                  total[5]=total[4]-i*coin[4]
                  for i in range(int(total[5]/coin[5])+1):
                      total[6]=total[5]-i*coin[5]
                      for i in range(int(total[6]/coin[6])+1):
                          total[7]=total[6]-i*coin[6]
                          count+=1

print count
4

3 に答える 3

2

Python制約ライブラリであるhttp://labix.org/python-constraintを参照することをお勧めします。そのサンプルファイルの1つは、実際には特定の量に到達するためのコインの順列であり、ルールを指定すると、すべてがそれを処理します。

于 2012-06-20T22:35:19.333 に答える
1

  1. すべての int キャストを取り除くことができます。int/int は依然として Python の int です。つまり、整数除算です。

  2. 再帰がこれをきれいに片付けるように見えます

    count  = 0
coin=[200,100,50,20,10,5,2,1]
total=[200,0,0,0,0,0,0,0]

def func(i):
    global count,total,coin
    for x in range(total[i-1]/coin[i-1]+1):
        total[i]=total[i-1]-x*coin[i-1]
        if (i == 7):
            count += 1
        else:
            func(i+1)

    func(1) 印刷回数

于 2012-06-20T23:43:51.567 に答える
0 
combinations = set()
for i in range(len(coins)):
  combinations = combinations | set(for x in itertools.combinations(coins, i) if sum(x) == 200)
print len(combinations)

少し遅いですが、動作するはずです。

于 2012-06-20T22:41:10.697 に答える