240. 최적의 상자 스택
-
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))
Author And Source
이 문제에 관하여(240. 최적의 상자 스택), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@corone_hi/240.-최적의-상자-스택저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)