240.最適な箱の積み重ね

7289 ワード
アルゴリズム#アルゴリズム# テキストリンク
Box stacking Problem

  • Consider, we have been given 3-Dimensional boxes. Each box has width, depth and height (wi, di, hi).

  • Box stacking problem is to stack these boxes in such a way that we achieve maximum height.

  • There is one condition that is attached to it: A box can be placed on top of another only if both it’s base dimensions width and depth are less than a box on which it stacked on. There is no restriction on height, a tall box can be placed on a short box.

    • 1. Python

    
def tallestStack(boxes):
    boxes.sort(key = lambda x: x[0])
    heights = {box: box[2] for box in boxes}

    for i in range(1, len(boxes)):
        box = boxes[i]
        S = [boxes[j] for j in range(i) if canBeStacked(boxes[j], box)]
        heights[box] = box[2] + max([heights[box] for box in S], default = 0)
        
    return max(heights.values(), default = 0)

def canBeStacked(top, bottom):
	return top[0] < bottom[0] and top[1] < bottom[1]

boxes = [(1,5,4), (1,2,2), (2,3,2), (2,4,1), (3,6,2), (4,5,3)]

print(tallestStack(boxes))
    Project | React - Webucks Clone Coding [Mission 4]
    自分で再ロックを実現