问答

当前位置
  • 首页
  • 问答
  • LeetCode 92 经典背包课程 01背包超时

LeetCode 92 经典背包课程 01背包超时

  • Ta: 衡助教

根据背包课程中老师讲的方法,采取体积作为背包值的做法。在提交中,testcase跑到78%的时候,超时。求指点!

def backPack(self, m, A):
staMap = [ [0 for i in range(m+1)] for j in range(len(A)+1) ]

    for i in range(len(A)+1):
        for j in range(m+1):
            if i==0 or j==0:
                staMap[i][j] = 0
            elif A[i-1]>j:
                staMap[i][j] = staMap[i-1][j]
            else:
                staMap[i][j] = max(staMap[i-1][j], staMap[i-1][j-A[i-1]]+A[i-1])

    return staMap[len(A)][m]

1 个回复

2019-09-11 Anidlebrain

这应该python本身就慢的原因引起的。
建议优化:staMap 改成bool型的类型进行运算

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1