ProjectEuler 201,多维背包
http://projecteuler.net/problem=201
寻找100个数里面，50大小的子集的，所有和唯一的子集的，和。
比普通背包多了一个子集数。
没计算最大可能的数是多大，直接用了python的字典表示“和” 的那个维度, 当然可以用滚动数组，或者临时变量啥的来减少一个维度，不过我直接每处理一行之后把上一行del， 这样可以简单些。。。
def main():
#define
N = 100
K = 50
num = [a*a for a in range(1, N+1)]
#initial
dp=[]
for i in range(N+1):
t = []
for j in range(N+1):
t.append({})
dp.append(t)
dp[1][0] = {0: 1}
dp[1][1] = {num[0]: 1}
#dp
for i in range(2, N+1):
for j in range(0, i+1):
if N-i+j < K:
continue
if j > K:
break
dp[i][j] = dp[i-1][j].copy()
for key in dp[i-1][j-1]:
if key+num[i-1] not in dp[i][j]:
dp[i][j][key+num[i-1]] = dp[i-1][j-1][key]
else:
dp[i][j][key+num[i-1]] += dp[i-1][j-1][key]
tmp = dp[i-1]
dp[i-1] = {}
del tmp
#outputs
print sum(key for key in dp[N][K] if dp[N][K][key] == 1)
if __name__ == '__main__':
main()
Back