搜狗面试题：有N个正实数(注意是实数，大小升序排列) x1 , x2 … xN，另有一个实数M。 需要选出若干个x，使这几个x的和与 M 最接近。 请描述实现算法，并指出算法复杂度。
分析：可以当做01背包问题及路径记录问题。
01 背包：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
落实到此题上：M为背包总容量，N个正实数的值 x1 , x2 … xN为物品的重量和价值，其中，重量和价值是一样的。
python代码：（使用二维dp才能记录路径）
def bag_problem1(bag_size, weight, value):
rows, cols = len(weight), bag_size+1
dp = [[0 for _ in range(cols)] for _ in range(rows)]
path = [[0 for _ in range(cols)] for _ in range(rows)]
#初始化dp数组
for i in range(rows):
dp[i][0] = 0
first_item_weight, first_item_value = weight[0],value[0]
for j in range(1, cols):
if j >= first_item_weight:
dp[0][j] = first_item_value
path[0][j] = 1
#更新dp数组，先遍历物品，再遍历背包
for i in range(1, rows):
for j in range(1, cols):
if weight[i] <= j and value[i] + dp[i - 1][j - weight[i]] > dp[i - 1][j]:
dp[i][j] = value[i] + dp[i - 1][j - weight[i]]
path[i][j] = 1
else:
dp[i][j] = dp[i - 1][j]
# if j <= weight[i]:
# dp[i][j] = dp[i-1][j]
# else:
# dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i])
print(dp)
print(path)
return path
if __name__ == '__main__':
bag_size = 100
weight = [90,7,4]
value = [90,7,4]
path=bag_problem1(bag_size, weight, value)
print("choose item ", end="")
tmp = bag_size
for i in range(len(weight) - 1, -1, -1):
if path[i][tmp] == 1:
print(i, end=" ")
tmp -= weight[i]
python代码：（一维dp）
def bag_problem2(weight, value):
# weight = [90,4,7]
# value = [90,4,7]
bag_weight = 100
# 初始化：全为0
dp = [0] * (bag_weight+1)
# 先遍历物品，再遍历背包容量
for i in range(len(weight)):
for j in range(bag_weight, weight[i]-1,-1):
dp[j] = max(dp[j],dp[j-weight[i]]+value[i])
print(dp)
print(bag_problem2([90,4,7],[90,4,7]))
参考文献：
[1] https://blog.csdn.net/weixin_34343000/article/details/86190458
[2] https://www.codeleading.com/article/89012160265/
[3] https://www.cnblogs.com/javathread/archive/2011/10/17/2635000.html
[4]https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html#%E4%BA%8C%E7%BB%B4dp%E6%95%B0%E7%BB%8401%E8%83%8C%E5%8C%85
[5]https://blog.csdn.net/NickHan_cs/article/details/107964648
[6]https://blog.nowcoder.net/n/87d01896e8db4ddb946f52840e8a3e2c?from=nowcoder_improve
