请教一道 Python 题目，感觉有点类似背包问题，我现在的代码太慢，请问有什么提速思路？
有给定的底面积 = 1，高度为 blocks 不等的积木；现在有一个底面积为 tong_size 的桶，想把积木全部放进去，求最低的堆积方案。
或者就是把一个数组分组，求分成n组之后，每一组的和的最大值为最小。
现在的代码方案是：
def mdp(tong_size, blocks): def guess():
tongs = [0] * tong_size
for indi, num in enumerate(blocks):
tongs[indi % tong_size] += num
return max(tongs)
def dp(tongs, i):
nonlocal tallest
if i == len(blocks):
tmp = max([sum(j) for j in tongs])
if tmp < tallest:
tallest = tmp
print(tongs, tmp)
return tmp
ret = []
for off, tong in enumerate(tongs):
if (off == 0 or sum(tong) + blocks[i] <= sum(tongs[off - 1])) and sum(tong) + blocks[i] < tallest:
# 每一列都只会比前面矮或者持平，但第一列是不限制 ，且每一列都要比最高列矮
tong.append(blocks[i])
ret.append(dp(tongs, i + 1))
tong.pop()
return min(ret) if ret else tallest
blocks.sort(reverse=True)
tallest = guess() # 写死的规则放一下，搜索出来的方案必须比这个矮
tongs = []
for i in range(tong_size):
tongs.append([])
tongs[0].append(blocks[0])
return dp(tongs, 1)
这个方案在解：
blocks = [2,2,6,5,4,6,3,5,4,6,2,2,6,5,4,2,2,6,5,4,6,3,5,4,6,2,2,6,5,4]
tong_size = 3
时，耗时超过10分钟。
我自己思考了一下可能的问题：
- 里面有重复数字，现在的检索，会尝试把 blocks[0] 放到某一列，然后后续又会尝试把 blocks[1] 放到同一位置，但是实际上是不改变结果的，但是没有跳过这类检索的思路。
- 可以快速计算出桶的最低高度，这样第一列一定要达到最低高度才需要进入下一列，但是也没有太好的实现思路。
回答：
- 求和三分（底为3），确定可能的最低堆积高度
- 对源数组排序，分入三数组
- 以数组和差绝对值两两最小为准绳,适时调整最大和数组与最小数组和中的最大与最小元素
blocks = [2,2,6,5,4,6,3,5,4,6,2,2,6,5,4,2,2,6,5,4,6,3,5,4,6,2,2,6,5,4]tong_size = 3
blocks.sort()
minH = sum(blocks)//3
print(sum(blocks),minH)
a,b,c = [],[],[]
for i in range(len(blocks)):
if sum(a)< minH:
a.append(blocks.pop())
elif sum(b)< minH:
b.append(blocks.pop())
else:
c = blocks
print(a,sum(a))
print(b,sum(b))
print(c,sum(c))
print("********")
# 将最大和的最大值元素与最小和最小元素交换
c.append(b.pop(0))
b.append(c.pop(0))
print(a,sum(a))
print(b,sum(b))
print(c,sum(c))
输出
124 41[6, 6, 6, 6, 6, 6, 6] 42
[6, 5, 5, 5, 5, 5, 5, 4, 4] 44
[2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4] 38
********
[6, 6, 6, 6, 6, 6, 6] 42
[5, 5, 5, 5, 5, 5, 4, 4, 2] 40
[2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 6] 42
42 为三数组和差值最小时的高度
以上是 请教一道 Python 题目，感觉有点类似背包问题，我现在的代码太慢，请问有什么提速思路？ 的全部内容， 来源链接： utcz.com/a/163013.html
