堆箱子

[编程题]堆箱子

热度指数：6930 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知三个int数组w,l,h，分别表示每个箱子宽、长和高，同时给定箱子的数目n。请设计算法，将箱子都堆起来（箱子不能反转），且上面箱子的宽度和长度必须小于下面的箱子。返回值为能够堆出的最高的高度。要求n小于等于500。

测试样例：

[1,1,1],[1,1,1],[1,1,1]

返回：1

算法知识视频讲解

Python

雷凌云

class Box:
    """
    lis 用来存放以boxes[i]为底的箱子之和的最大值。
    当boxes[j]的长宽<boxes[i]的长宽时（j<i），boxes[i]可以放到boxes[j]的下面。
    将boxes[i]与之前的底逐一比较，求出最大值，即为lis[i]的值。
    """
    def getHeight(self, w, l, h, n):
        boxes = [(w[i], l[i], h[i]) for i in range(n)]
        boxes.sort()
        lis = [boxes[i][-1] for i in range(n)]
        for i in range(1, n):
            for j in range(i):
                if boxes[j][0] < boxes[i][0] and boxes[j][1] < boxes[i][1]:
                    h = lis[j] + boxes[i][-1]
                    if lis[i] < h:
                        lis[i] = h
        return max(lis)

发表于 2019-07-22 22:09:31 回复(0)

Python

Yannyezixin

# -*- coding:utf-8 -*-
class Box:
    def getHeight(self, w, l, h, n):
        if n <= 0:
            return 0
        
        box = [(w[i], l[i], h[i]) for i in range(n)]
        box.sort(key = lambda b: (b[0], b[1]), reverse=True)
        height = [0] * n
        
        for i in range(n):
            height[i] = box[i][2]
            for j in range(i - 1, -1, -1):
                if box[j][0] > box[i][0] and box[j][1] > box[i][1]:
                    height[i] = max(height[i], height[j] + box[i][2])
        return max(height)

发表于 2016-08-08 07:23:59 回复(0)