포장 사용 계산 알고리즘

Question

특정 크기의 영역이 주어지면 해당 영역을 완전히 포장하는 데 사용할 포장 돌의 수를 알아야합니다. 나는 20x10cm와 30x10cm 크기의 100 미터 사각형과 돌로 된 빈 바닥이 있다고 가정합니다. 나는 양쪽 크기의 돌을 최소한으로 사용하여이 지역을 포장해야합니다. 누구든지 이것을 계산하는 알고리즘을 알고 있습니까? (내 영어 나쁜 경우 죄송합니다)

은

C#을하는 것이 바람직하다.

Answer 1

이것은 포장 문제로 알려진 문제의 범주입니다.

이 DevX article은 숙제를 직접 해결하지 않고도 배경과 개요를 제공합니다 (코드도 제공하지만 상황에 맞게 적용해야합니다).

Answer 2

머리 부분에서이를 해결할 수 있습니다 (채울 영역이 직사각형이라고 가정). N 개의 사각형 영역을 채우고 타일이 2x1 및 3x1 인 경우 2x1 타일을 2 개 이상 필요하지 않습니다. 불가능한 N = 1 경우를 제외하고 필요한 타일의 총 수는 N/3 (반올림)입니다.

증명 : 당신의 영역을 가정 것은 X의 B이고, 둘 다 A와 B의입니다 1. 일반성의 손실없이 가정이 A = 것을 1

할 수 있습니다 타일 직사각형 영역 (A) × 3으로! 3x1 타일 쉽게. 이 패턴을 반복하여 가능한 한 많이 채 웁니다. 왼쪽 행이 없으면 작업이 끝났습니다 (3x1 타일로 전체 영역을 바둑판 식으로 배열했습니다). 한 행이 남아 있으면 0, 1 또는 2 공백이 남을 때까지 3x1 타일로 채 웁니다. 0 => 끝났습니다. 1 => 마지막 3x1을 두 개의 2x1로 바꾸고, 2 => 마지막 사각형을 2x1로 채 웁니다. 왼쪽에 두 개의 행이 있으면 비슷한 구조로 수행하십시오. 0 열 (완료), 1 열 (2x1로 채우기) 또는 2 열 (두 개의 2x1로 채 웁니다.) 중 하나가됩니다.