木板切割攻略(关于木板切割最优问题怎么做,有哪些方法?)

木板切割攻略(关于木板切割最优问题怎么做,有哪些方法?)，给大家带来详细的木板切割攻略(关于木板切割最优问题怎么做,有哪些方法?)介绍，大家可以阅读一下，希望这篇木板切割攻略(关于木板切割最优问题怎么做,有哪些方法?)可以给你带来参考价值。

这是一个经典问题，在维基百科上有相应词条。在这里进行简单介绍，请大家尊重学术规范，不要抄袭

​

木工切割木板，每刀必须从一边开始到一边结束，否则如果运刀长度不精确木板切割攻略，太短则切不下来，太长则会在另一块木板上留下切口。

因此木板切割攻略，每切割一刀都会把一块木板分割成宽度相同的两部分。可以根据刀口位置进行递推: S(i,j)是长为i，宽为j的木板可以切割成小木板的最多的数目。l, w分别是小木板的长和宽，L, W分别是大木板的场合款。

边界条件

可以利用对称性S(i,j)=S(j,i)加速。另外还可以根据l和w的数字关系进行优化。最后算出3000x1500里面切出373x201最多的块数是59，切割方式如下

最优切法

比完全填充

只少了1块

Mathematica代码贴在了下面，因为不会爆内存所以写得比较铺张浪费，实际需要算的S（代码里面写的是v）是很稀疏的，所以可以存得更加紧凑

{L, W} = {3000, 1500};
{l, w} = {373, 201};
numberOfInterest =
  Select[Outer[Plus, Range[0, L, l], Range[0, L, w]] // Flatten //
      Sort, #  L &]~Append~(L + 1) // DeleteDuplicates;
noi = Rest@numberOfInterest;
noiDict =
  Table[ConstantArray @@ seg, {seg,
     Transpose[{Most@numberOfInterest,
       Differences@numberOfInterest}]}] // Flatten;
v = ConstantArray[-1, {L, L}];
Do[v[[j, i]] = v[[i, j]] = Floor[i/l] Floor[j/w], {i, 1, L}, {j, 1,
   l - 1}];
dp[i_, j_] := Module[{ii, jj, ik, jk},
  If[v[[i, j]] >= 0, Return[v[[j, i]] = v[[i, j]]]];
  If[v[[j, i]] >= 0, Return[v[[i, j]] = v[[j, i]]]];
  {ii, jj} = noiDict[[{i, j} + 1]];
  If[ii == i && jj == j,
   ik = Select[noi, (w  #  i - 1) &];
   jk = Select[noi, (w  #  j - 1) &];
   v[[j, i]] = v[[i, j]] = Max[
      Table[dp[k, j] + dp[i - k, j], {k, ik}],
      Table[dp[i, k] + dp[i, j - k], {k, jk}],
      1
      ],
   v[[i, j]] = v[[j, i]] = dp[ii, jj]
   ]
  ]

用来输出方案图的代码

标签组： [木板]