习题3.1
递归式和边界条件：
其中 表示的是只考虑前 个函数，并且满足 的子问题的解。
伪代码：
时间复杂度： ，其中 是函数的个数， 是限制条件的大小。
def FindMaxObjectValue():
dp = {}
# 记录当子问题取最大值时，给gk分配了的x多大。
solution = {}
# 设置边界条件。
for y in range(0, MAX_Y + 1):
dp[1, y] = g[1][SquareRootFloor(y)]
solution[1, y] = SquareRootFloor(y)
sum = 0
for k in range(1, MAX_K + 1):
sum += g[k][0]
dp[k, 0] = sum
solution[k, 0] = 0
for k in range(2, MAX_K + 1):
for y in range(1, MAX_Y + 1):
print('k', k, 'y', y)
val = -1
sol = None
for xk in range(0, SquareRootFloor(y) + 1):
temp = dp[k - 1, y - xk * xk] + g[k][xk]
if temp > val:
val = temp
sol = xk
dp[k, y] = val
solution[k, y] = sol
max_val = dp[MAX_K, MAX_Y]
return max_val
def SquareRootFloor(x):
return int(math.sqrt(x))
