碰到最初看起来非常简单的问题;但是，我找不到有效的解决方案 . 你们能帮忙吗？
片材由具有间隙但不相交的各种长度和宽度的矩形（框架）组成 . 找到将这些矩形分开的最少量的直切（垂直或水平） . 切割必须通过整个可用的板 .
输入由矩形的数量组成，后面是每个矩形的左上角和右下角坐标 . 输出应具有切割次数，然后是2个点，表示垂直/水平切割或NA，如果没有解决方案 . 请注意，可以使用几种最佳解决方案
Input:
（3,3）
（0,0）（1,1）
（2,0）（3,1）
（0,2）（3,3）
Output:
2
（0,2）（2,2）
（1,0）（1,2）
Input:
（5,5）
（0,0）（3,1）
（4,0）（5,3）
（0,2）（1,5）
（2,4）（5,5）
Output:
NA
1 回答
这是P. Y.Wang自下而上的二维算法（作为一种可能的方法）解决的切割股票问题的典型例子 .
Google搜索链接通常会导致付费访问文章，但也可以找到一些publically available描述（PDF version，第6页）