请教一道 Python 题目,感觉有点类似背包问题,我现在的代码太慢,请问有什么提速思路?

echoing
  • 46

有给定的底面积 = 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分钟。

我自己思考了一下可能的问题:

  1. 里面有重复数字,现在的检索,会尝试把 blocks[0] 放到某一列,然后后续又会尝试把 blocks[1] 放到同一位置,但是实际上是不改变结果的,但是没有跳过这类检索的思路。
  2. 可以快速计算出桶的最低高度,这样第一列一定要达到最低高度才需要进入下一列,但是也没有太好的实现思路。
回复
阅读 560
1 个回答
  1. 求和三分(底为3),确定可能的最低堆积高度
  2. 对源数组排序,分入三数组
  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 为三数组和差值最小时的高度

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏