Задача двумерной упаковки квадратов в прямоугольнике

[joparezzz]

Версия AutoIt: 3.3.0
Описание:
Есть квадраты стороной 20, 30, 40, 60, 90, 120 мм.
Количество квадратов задается в исходных данных.

Указанные квадраты необходимо разместить в прямоугольник шириной 120 мм, а длина не должна превышать 180 мм.
1. Размещать квадраты внутри прямоугольника необходимо начиная с наибольших квадратов.
2. В одной линии можно размещать разные квадраты, например 60 мм - 1 шт. и 30 мм 4 шт. или 40 мм - 2 шт. и 20 мм - 4 шт.
3. Если квадраты не умещаются в прямоугольник 120х180 мм, необходимо создать еще 1 прямоугольник шириной 60 или 120 мм, при этом длина первого прямоугольника и вновь созданного должны совпадать.
4. Если квадраты закончились и какой-то ряд в прямоугольнике остался не заполненным, то необходимо добавить квадраты и каким-то образом пометить их (на примере, во вложении, закрашено желтым).
Ответ, для начала, можно выводить просто в консоли, например, так: для размещения квадратов 60 мм – 2шт., 40 мм – 5 шт., 30 мм – 2 шт., необходим 1 прямоугольник шириной 120 мм длиной 170 мм:
Ряд 1: 60 мм – 2 шт.;
Ряд 2: 40 мм – 3 шт.;
Ряд 3: 40 мм – 3 шт. (1 из них доп.);
Ряд 4: 30 мм – 4 шт. (2 из них доп.).

Примечания:
В последствии, можно, ответ выводить графически.

 

[Garrett]

joparezzz

Правила обязательного оформления тем в разделе "Стол заказов"

 

[NickSpirit]

Однако довольно сложная задача с довольно сложным алгоритмом. Причем данная штука оч полезна в промышленности))) Например для раскроя металлических листов. Это я все к чему - нужно иметь оч огромное желание и интерес чтобы заняться данной задачей. Интерес у меня есть а вот желания никакого). (именно за просто так). Но задача оч интересная на самом деле.

 

[sergioz]

#include <Array.au3>
Opt('MustDeclareVars',1)
Global Const $List_w=18
Global Const $List_h=12
;массив с фигурами
;Dim $sq[6][3]=[[3,2,2],[2,3,3],[2,4,4],[2,6,6],[1,9,9],[2,12,12]]
;Global Const $sq_col=0;количество квадратов
;Global Const $sq_w=1;ширина
;Global Const $sq_h=2;высота
;массив с фигурами
Dim $list[$List_w][$List_h]
_find_mark($list,1,9,9)
_find_mark($list,2,6,6)
_find_mark($list,3,4,4)
_find_mark($list,4,3,3)
if not _find_mark($list,8,9,9) Then MsgBox(0,"","no room!")
_ArrayDisplay($list)
Func _find_mark(ByRef $list,$sign,$dim_W,$dim_H)
Local $i,$j,$k,$l,$switch
   for $i=0 To $List_w-1
	  for $j=0 to $List_h-1
$switch=0
	  For $k=0 to $dim_W-1
		 For $l=0 to $dim_H-1
			if $i+$k>=$List_w or $j+$l>=$List_h Or $list[$i+$k][$j+$l]>0 then
			   $switch=1
			   ExitLoop
			EndIf
		 Next
		 if $switch=1 then ExitLoop
	  Next
	  if $switch=0 Then
		 For $k=0 to $dim_W-1
			For $l=0 to $dim_H-1
			  $list[$i+$k][$j+$l]=$sign
			Next
		 Next
		 ExitLoop
	  EndIf
	  Next
	  If $switch=0 Then ExitLoop
   Next
if $switch=1 then Return 0
EndFunc

задача для старшей школы. функцию размещения квадов(да и любых др. прямоуглов) я написал. дальше вам 5 минут делов цыклы наделать по количеству элементов