1

我想知道有多少种方法可以仅使用 1、2、5、10、20、50、100 和 200 来制作 500。我知道存在可以解决此类问题的贪婪算法等，但我希望能够通过以下方式做到这一点：

给定数 n 的整数分区数，仅使用某个集合 T 中的数，可以从所有 (1-x t ) -1乘积中的 x n项的系数获得，其中 t 在 T .

为此，请注意 (1-x t ) -1的泰勒展开式等于 (1+x t +x 2t +...)。这是我到目前为止编写的代码：

#################################
# First, define a function that returns the product of two 
# polynomials. A list here
# represents a polynomial with the entry in a list corresponding to 
# the coefficient of the power of x associated to that position, e.g. 
# [1,2,3] = 1 + 2x + 3x^2.
#################################

def p(a,v):
    """(list,list) -> list"""
    prodav = [0]*(len(a)+len(v)-1)

    for n in range(len(a)):
        for m in range(len(v)):
            prodav[n+m] += v[m]*a[n]

    return prodav

#################################
# Now, let a,b,c,...,h represent the first 501 terms in the Taylor 
# expansion of 1/(1-x^n), where n gives the coin value, i.e 
# 1,2,5,10,20,50,100,200 in pence. See the generating function
# section in https://en.wikipedia.org/wiki/Partition_(number_theory).
# Our function, p, multiplies all these polynomials together
# (when applied iteratively). As per the Wiki entry, the coefficient 
# of x^t is equal to the number of possible ways t can be made,
# using only the denominations of change available, a so called 
# 'restricted integer partition'. Note that it isn't necessary to 
# consider the entire Taylor expansion since we only need the
# 500th power.
#################################

a = ( [1]           ) * 501            #   1
b = ( [1] + [0]     ) * 250 + [1]      #   2
c = ( [1] + [0]*4   ) * 100 + [1]      #   5
d = ( [1] + [0]*9   ) *  50 + [1]      #  10
e = ( [1] + [0]*19  ) *  25 + [1]      #  20
f = ( [1] + [0]*49  ) *  10 + [1]      #  50
g = ( [1] + [0]*99  ) *   5 + [1]      # 100
h = ( [1] + [0]*199 ) *   2 + [0]*101  # 200

x = p(h,p(g,p(f,p(e,p(d,p(c,p(b,a)))))))

print(x[500])  # = 6290871

我的问题是我不确定这个给出的答案是正确的。我已经将它与其他两种贪心算法进行了比较，它们的输出彼此一致，但不是我的。谁能看到我可能出错的地方？

4

0 回答 0