aimisiyou 发表于 2016-5-2 16:28:18

二维下料

二维下料
http://bbs.xdcad.net/thread-704088-1-1.html
(出处: 晓东CAD家园-论坛)

aimisiyou 发表于 2016-5-2 16:36:50

;;;;函数(CL DA DB a b)中DA——母材长;DB——母材宽;a——构件长;b——构件宽;(DA>=DB,a>b且a不能是b的倍数)
;;;;所得结果为表形式,如(CL 9000 4000 600 480)=((2 5 2 40 3600) (2 3 0 0 1440) (1 1 1 40 1080) (1 1 0 120 480) (1 1 0 40 480) (240 640))
;;;;表中最后一项(240 640)表示最后剩下的一个不能被裁割的废料,第一项如(2 5 2 40 3600)中首项2表示系数,中间5,2表示宽度方向为5a+2b;最后两项40,3600表示经这次裁料后余下的废料边长
;;;;所能得到的构件个数为2*(5+2)^2+2*(3+0)^2+1*(1+1)^2+1*(1+0)^2+1*(1+0)^2=120块,离上限数9000*4000/600/480=125还算接近
;;;;若小构件为正方形a*a,则母板能裁下的构件数为n=*;所以当a是b的倍数时,即a=k*b,则能获得的构件数为n=k**+边角料能获得构件a*b的个数
;;;;最后说明,(a,b)必须经过各自倍增后所得差值最小,如(CL200 100107)结果有误,应先进行(CL 200 100 21 20),再对废料按(10,7)裁割
(defun ff (n / llist i)
   (setq llist '() i 0)
   (while (<= i n)
       (setq llist (cons i llist))
       (setq i (+ i 1))
    )
    llist
)
(defun qz (x y)
   (setq n (/ (- x (rem x y)) y))
)
(defun zg(DA DB a b)
   (setq nlist nil)
   (foreach na (ff (qz DB a))
      (foreach nb (ff (qz (- DB (* a na)) b))
               (if (and (< (- DB b) (setq sum_A (+ (* a na) (* b nb)))) (>= DB sum_A) )
                   (setqnlist (cons (list na nb (- DB sum_A) (+ (* b na) (* a nb))) nlist))
               )            
         )
    )
   nlist
)
(defun px(lst)
(car (vl-sort (vl-remove nil (mapcar '(lambda (x) (if (= (caddr x) (apply 'min (mapcar '(lambda (y) (caddr y)) lst) ) ) x nil)) lst)) '(lambda (x y) (> (car x) (car
y))) ))
)
(defun count(DA DB a b)
   (setq lst (px (zg DA DB a b)))
   (setq x (cadr lst))
   (setq y (car lst))
   (setq sum (+ (* a x) (* b y)))
   (if(= (rem DA sum) 0)
      (setq num (/ DA sum))
      (setq num (+ (/ (- DA DB) sum) 1))
   )
(cons num lst)
)
(defun CL(DA DB a b)
   (if (or (< DA a) (< DB b))
       (setq lst (list (list DB DA)))
       (setq lst (cons (setq zlst (count DA DB a b)) (CL DB (- DA (* (car zlst)(last zlst))) a b) ))
   )
)
(CL 9100 3800 350 300)

aimisiyou 发表于 2016-5-3 23:43:37

本帖最后由 aimisiyou 于 2016-5-4 00:05 编辑

DB=k1*a+k2*b,(k1,k2互质)那么构成的矩形另一边为k2*a+k1*b;如果沿每行方向看每个构件的放置情况,横放为1,纵放为0,那么构成的(k1+k2)*(k1+k2)矩阵每行中有k2个1,k1个0。那么给定k1,k2,怎么得到这个矩阵g(k1,k2)呢?

aimisiyou 发表于 2016-5-4 00:03:04

\[ g(1,1) = \begin{pmatrix}
0& 1 \\
1 & 0\end{pmatrix}_{1 \times 1 } ,
g(2,1) = \begin{pmatrix}
0& 1&0 \\
0 & 0&1\\1&0&0\end{pmatrix}_{3 \times 3 }, g(3,2) = \begin{pmatrix}
1 & 0&0&0&1 \\
0 & 1&0&1&0\\0&0&1&1&0\\1&0&1&0&0\\0&1&0&0&1\end{pmatrix}_{5 \times 5 }\dots \]

aimisiyou 发表于 2016-5-5 23:37:31

本帖最后由 aimisiyou 于 2016-5-6 00:09 编辑

闂??鏁寸悊鍚庡綊绾冲?涓嬫眰f(i,j)锛

补充内容 (2016-5-6 09:11):
怎么手机上编辑后是乱码?

aimisiyou 发表于 2016-5-6 09:25:55

本帖最后由 aimisiyou 于 2016-5-6 14:43 编辑

问题归纳为找f(i,n-i)=A_n*n,A_n*n其满足以下条件
1、i,n-i互质;
2、每行有(n-i)个1,i个0;且每列有(n-i)个1,i个0;
3、A_n*n中的每个子项A_x*y(1<x<=n,1<y<=n)每列sum值任意相邻两列差值不超过1;且同样每行sum值任意相邻两行差值不超过1。
f(6,5)有哪些?
若将条件3加强,将“任意相邻”改为“任意”,对于加强版F(i,n-i)是否必然有解?显然F(i,n-i)也是f(i,n-i)的解。谁能试算F(6,5)情况?
f(i,n-i)通过置换很容易得到一部分,而F(i,n-i)在什么情况下有解?解有哪些?可能更有意义。

aimisiyou 发表于 2016-5-6 09:59:15

本帖最后由 aimisiyou 于 2016-5-6 10:01 编辑

F(1,1) = \begin{pmatrix}
0& 1 \\
1 & 0\end{pmatrix}
F(2,1) = \begin{pmatrix}
0& 1&0 \\
0 & 0&1\\1&0&0\end{pmatrix}
F(3,2) = \begin{pmatrix}
1 & 0&0&0&1 \\
0 & 1&0&1&0\\0&0&1&1&0\\1&0&1&0&0\\0&1&0&0&1\end{pmatrix}
等号后面只是其中的一个解。

aimisiyou 发表于 2016-5-9 21:15:44

谁有求F(i,n-i)好的算法吗?

BeerRabbit 发表于 2016-5-19 18:57:23

Lisp代码看着真是费劲………………

aimisiyou 发表于 2016-5-19 20:12:34

F(13,9)如下
页: [1] 2
查看完整版本: 二维下料