经典动态规划问题，任务分配插值最小

weight = [1, 2, 7, 3, 6, 4, 2, 3, 8, 9, 1, 23, 6, 22]
n = len(weight)
m = (sum(weight)+1)//2
#动态规划表，多放置了0行0列,方便计算
optp = [[0 for i in range(m+1)]for j in range(n+1)]for j in range(1,n+1):for i in range(1, m+1):# 总是和前一行的比较if weight[j-1]<i:# 如果放进去了，和剩余的最大值相加optp[j][i] = max(optp[j - 1][i], weight[j - 1] + optp[j - 1][i - weight[j - 1]])else:optp[j][i] = optp[j - 1][i]
for j in range(1,n+1):print(optp[j])
total = optp[-1][-1]#计算放置目标重量集和剩余集
lres, rres = [], []
for j in range(n, 0, -1):if optp[j][total+1]>optp[j-1][total+1] and total>=0:lres.append(weight[j-1])total -= weight[j-1]else:rres.append(weight[j-1])
print(lres)
print(rres)