더 큰 직사각형 상자에 직사각형 상자 배치

다른 크기의 직사각형 상자와 더 큰 직사각형 상자가 있습니다. 큰 상자에 가능한 여러 카테고리의 상자를 최대한 넣어야합니다. 어떤 범주에 속해 있더라도 최소한의 상자 수만큼 수용해야합니다. 기본적으로 제약 조건 최적화 문제를 해결해야합니다. 어떻게해야합니까?더 큰 직사각형 상자에 직사각형 상자 배치

출처

2013-03-29 noddy

같은 카테고리의 모든 상자는 같은 크기입니까? –

사용 가능한 각 위치에 다음 상자를 배치하는 brute-force 재귀 방식을 사용하기로 결정한 경우 최적의 솔루션을 잃지 않고 솔루션 공간을 축소하는 한 가지 방법은 새 상자 배치를 제한하여 항상 왼쪽과 아래쪽에있는 기존 상자 (또는 포함 된 상자의 벽)를 만져야합니다. 이는 모든 솔루션이 더 이상의 이동이 가능하지 않을 때까지 상자를 왼쪽과 아래로 반복적으로 이동함으로써 모든 상자가이 제약 조건을 준수하는 솔루션으로 변형 될 수 있기 때문에 가능합니다. –

사각형 상자는 2D 또는 3D입니까? –

이 문제에 대한 다항식 시간 알고리즘은 없습니다. 즉 NP가 어렵습니다.

그래서 검색해보십시오. 큰 것부터 작은 것까지 상자를 정렬하면 도움이 될 수 있습니다 (지역별 또는 한쪽면 검색 방법에 따라 어느 쪽이 더 좋을지 말할 수 없음).

속도가 허용 범위를 훨씬 벗어나는 경우 다소 좋은 해결책을 얻으려면 욕심이 많습니다.

출처

2013-03-29 07:43:05 Topro

실제로 NP-Hard의 문제점을 알고 있으므로 대략적인 해결책을 찾고 있습니다. 나는 문제를 계속할 수있는 방법을 생각할 수 없다. – noddy

오 ... 나는 그때를 모른다. 현실 세계의 문제라면 욕심이 좋을 것 같습니다. 그렇지 않으면 당신은 스타 (A *)를보고 좋은 평가 기능을 찾아보십시오. – Topro

더 큰 직사각형 상자에 직사각형 상자 배치

답변

관련 문제