二维下料

aimisiyou

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

aimisiyou

;;;;函数（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=[DA/a]*[DB/a];所以当a是b的倍数时，即a=k*b,则能获得的构件数为n=k*[DA/a]*[DB/a]+边角料能获得构件a*b的个数
;;;;最后说明，(a,b)必须经过各自倍增后所得差值最小，如（CL  200 100  10  7）结果有误，应先进行（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) )
                   (setq  nlist (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

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

\[ 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

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

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

aimisiyou

问题归纳为找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

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

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

BeerRabbit

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

aimisiyou

F(13,9)如下