1
좋아하는 브라우니 제조법을 올리고 새로운 9x3 인치 베이킹 접시에 부어 넣으십시오. 브라 우니가 빵 굽는다. 이쑤시개가 깨끗하게 나온다. 자르면.9 x 3 rect를 8 등각 크기로 나누십시오.
사각형은 브라우니에게 가장 맛있는 모양입니다. 너는 봉사 할 사람이 8 명있다. 새롭게 구운 피조물을 어떻게 정확히 8 각형으로자를 수 있습니까?
A
답변
3
그래서 이것은 본질적으로 빈 패킹 문제에 대한 변형입니다 (이것은 NP -hard로 잘 알려져 있습니다!). 다양한 사각형의 위치가 될 수 있기 때문에
이 솔루션은 분명 아닌 고유 다음과 같이
하나의 솔루션으로, 2 개 3x3 사각형, 1 2x2 광장과 5 개 1x1 사각형을 사용하는 것입니다 주위 순회.
NP -hardness로 인해 일반적인 NxM 사각형을 k 개의 사각형으로 정확하게 분할하는 것은 어려운 알고리즘이라고 생각합니다. 실제로 솔루션을 사용할 수없는 매개 변수 값의 전체 패밀리가 있어야합니다 (예 : 6x1 직사각형으로 시작한 경우 6 개 미만의 정사각형으로 나눌 수 없음 ...).
8x 1in by 1in pieces, 분명히. – hkf
@hkf : 질문을 올바르게 이해 했습니까? – UPT
8 개의 정사각형 조각으로, 1x1 사각형 (실제로 입방체를 의미 할 때)이 동일합니까? 그렇지 않습니다. – hkf