砝码问题

nessunsweet

有一组砝码，重量互不相等，分别为m1、m2、m3……mn；它们可取的最大数量分别为x1、x2、x3……xn。
现要用这些砝码去称物体的重量,问能称出多少种不同的重量。
现在给你两个正整数列表w和n， 列表w中的第i个元素w[i]表示第i个砝码的重量，列表n的第
i个元素n[i]表示砝码i的最大数量。i从0开始，请你输出不同重量的种数。
如：w=[1,2], n=[2,1], 则输出5（分析：共有五种重量：0,1,2,3,4）


m = set()
for i in range(n[0]+1):
    m.add(w[0]*i)
for i in range(1,len(n)):
    tmp = m.copy()
    m.clear()
    for j in range(n[i]+1):
        for k in tmp:
            m.add(w[i]*j+k)
print len(m)

程序段的思路我搞不清楚，麻烦大家指教下~~

timespace

思路都差不多：找出n中所有对应砝码的数量组合，然后计算所有对应的重量与数量乘积的和，最后去重，完事。
实现么，大同小异，忍不住写了一行代码。

1. >>> from itertools import product
   
2. >>> w = [1, 2]
   
3. >>> n = [2, 1]
   
4. >>> set(sum(x*y for x,y in zip(w, e)) for e in product(*[range(e+1) for e in n]))
   
5. {0, 1, 2, 3, 4}

复制代码

q1208c

回复 1# nessunsweet
就是一个集合呀.