随机生成【0-50】区间内的十个数，使其总和等于100

时间：2011-06-01 来源：class

使用动态规划来求解问题

使用10*101的数组，l[i][j]表示随机i个的数，总和为j的所有可能性的数目。

那么l[i][j]=sum(l[i-1][k] for k in range(j-50,j+1) if k>=0)

使用1 到 l[i][j]中的每一个数字表示一种方案，

将 1到l[i][j] 分为 50个区间

1 到 l[i][j-50] ,1+l[i][j-50] 到 l[i][j-50]+l[i][j-49],1+l[i][j-50]+l[i][j-49]到 l[i][j-50]+l[i][j-49]+l[i][j-48]

随机出 1到l[10][100] 之间的数字，然后构造出一种方案。

View Code

def f():
    l=[[1]+[0 for i in range(100)]]
    for i in range(10): 
        l.append([sum(l[-1][k] for k in range(max(0,j-50),j+1)) for j in range(101)])
    def getlist():
        A=randint(1,l[-1][-1])
        t=100
        result=[]
        for i in range(9,0,-1):
            for j in range(max(0,t-50),t+1):
                if A<=l[i][j]:
                    result.insert(0,t-j)
                    t=j
                    break
                else:
                    A=A-l[i][j]
        result.insert(0,t)
        return result
    return getlist
get=f()
for i in range(100):
    print(get())