问题如下： 板材加工
工厂每天要把多个固定大小的长方形的模板（原料）切割成若干种不同长宽的方形的待加工品，
当然每种待加工品也有数量上的计划，我想计算怎么切割才是最省料的切法
注：1.每切一刀必须是一直到头的，（这个是和工厂的机器有关的）
2.待加工品暂不考虑有其他形状的可能，只有长方形，正方形
我的想法是，比如每天计划切8种材料，每种需要的个数不同，是不是要先切大的，然后看看剩的料切多少小的，
这其中要考虑这8种的面积，长宽，还有数量。
期待牛人的算法。有好的答案，我另开帖给分
7 个解决方案
#1
我感觉有点像是0-1背包问题，固定体积的书包大小，若干件不同体积的物品要放到其中，问选其中哪些物品能使书包最大利用。
这里固定的本板是书包，要切成的不同大小的块就是物品。所不同的是这里有很多个固定大小的背包，且要背的物品也很奇特——它只能“一刀切到尽头”。
暂时没有太明确的思路，如果不对，希望没有误导各位。
这里固定的本板是书包，要切成的不同大小的块就是物品。所不同的是这里有很多个固定大小的背包，且要背的物品也很奇特——它只能“一刀切到尽头”。
暂时没有太明确的思路，如果不对，希望没有误导各位。
#2
楼上说的是类似
#3
不一定先切大的就能达到最优
可以用搜索+剪枝
取面积为剪枝的判据
可以用搜索+剪枝
取面积为剪枝的判据
#4
貌似装箱问题的转化版，比较好的解法是近似算法中的首次适宜算法，复杂度O(n^2)。
下面是装箱问题的解法：
void first_fit(float s[],int n,float c,float b[],int &k)
{
int i,j;
k =0; //装入物体的箱子下标
for(i=0;i<n;i++)
b[i] = 0; //箱子初始化为空
for(i=0;i<n;i++){ //按物体顺序装入
j = 0;
while((c-b[j])<s[i]) //检索能容纳物体i的校标最小的箱子j
j++;
b[j]+=s[i];
k = max(k,j);
}
k++;
}
下面是装箱问题的解法：
void first_fit(float s[],int n,float c,float b[],int &k)
{
int i,j;
k =0; //装入物体的箱子下标
for(i=0;i<n;i++)
b[i] = 0; //箱子初始化为空
for(i=0;i<n;i++){ //按物体顺序装入
j = 0;
while((c-b[j])<s[i]) //检索能容纳物体i的校标最小的箱子j
j++;
b[j]+=s[i];
k = max(k,j);
}
k++;
}
#5
不过这个要比装箱复杂 在检索模板时模板的体积可能不是一个整体了。
因此可以将切割下来的原料都看做一个模板 然后再用最适宜算法进行类似装箱操作。
void first_fit(float s[],int n,float c,float LinkList L,int &k)
{
//用链表表示模板序列，方便添加和删除模板
int i;
Empty(L,c); //模板链表初始化
for(i=0;i <n;i++){ //按物体顺序装入
LinkList *p =L->next;
while(p){
.检索能容纳物体i的最小的模板节点p
.p->data-s[i]，这时模板节点p的data分为两个模板a,b
.创建新的模板节点:A->data = a;B->data = b;
.插入新模板 Insert(A);Insert(B);
}
}
}
因此可以将切割下来的原料都看做一个模板 然后再用最适宜算法进行类似装箱操作。
void first_fit(float s[],int n,float c,float LinkList L,int &k)
{
//用链表表示模板序列，方便添加和删除模板
int i;
Empty(L,c); //模板链表初始化
for(i=0;i <n;i++){ //按物体顺序装入
LinkList *p =L->next;
while(p){
.检索能容纳物体i的最小的模板节点p
.p->data-s[i]，这时模板节点p的data分为两个模板a,b
.创建新的模板节点:A->data = a;B->data = b;
.插入新模板 Insert(A);Insert(B);
}
}
}
#6
定义一个材料类，有长宽数量等属性
材料分为两类:原材料，目标材料。例如原材料 长9 宽9 数量9 目标材料:长7 宽5 数量 3 ；长 3 宽2 数量3
两种类型的材料都存到集合里面。
遍历原材料集合拿出一个材料。
再遍历目标材料集合。取最大的目标材料。进行切割。
原材料长减去目标材料长。原材料被分为两块。
原材料宽减去目标材料宽。原材料被分为三块。
处理完后，原材料分为两块可用。目标材料集合中数量减一
如果原材料的长宽不能被切割成最小的目标材料就废弃
分成的两块原材料有放入集合。迭代进行处理。直到原材料不能被处理。
依次进行处理直到所有原材料处理完
材料分为两类:原材料，目标材料。例如原材料 长9 宽9 数量9 目标材料:长7 宽5 数量 3 ；长 3 宽2 数量3
两种类型的材料都存到集合里面。
遍历原材料集合拿出一个材料。
再遍历目标材料集合。取最大的目标材料。进行切割。
原材料长减去目标材料长。原材料被分为两块。
原材料宽减去目标材料宽。原材料被分为三块。
处理完后，原材料分为两块可用。目标材料集合中数量减一
如果原材料的长宽不能被切割成最小的目标材料就废弃
分成的两块原材料有放入集合。迭代进行处理。直到原材料不能被处理。
依次进行处理直到所有原材料处理完
#7
数量不大的话，可以靠硬搜，数量大的话，还是找近似算法吧。应该属于NP级的。
#1
我感觉有点像是0-1背包问题，固定体积的书包大小，若干件不同体积的物品要放到其中，问选其中哪些物品能使书包最大利用。
这里固定的本板是书包，要切成的不同大小的块就是物品。所不同的是这里有很多个固定大小的背包，且要背的物品也很奇特——它只能“一刀切到尽头”。
暂时没有太明确的思路，如果不对，希望没有误导各位。
这里固定的本板是书包，要切成的不同大小的块就是物品。所不同的是这里有很多个固定大小的背包，且要背的物品也很奇特——它只能“一刀切到尽头”。
暂时没有太明确的思路，如果不对，希望没有误导各位。
#2
楼上说的是类似
#3
不一定先切大的就能达到最优
可以用搜索+剪枝
取面积为剪枝的判据
可以用搜索+剪枝
取面积为剪枝的判据
#4
貌似装箱问题的转化版，比较好的解法是近似算法中的首次适宜算法，复杂度O(n^2)。
下面是装箱问题的解法：
void first_fit(float s[],int n,float c,float b[],int &k)
{
int i,j;
k =0; //装入物体的箱子下标
for(i=0;i<n;i++)
b[i] = 0; //箱子初始化为空
for(i=0;i<n;i++){ //按物体顺序装入
j = 0;
while((c-b[j])<s[i]) //检索能容纳物体i的校标最小的箱子j
j++;
b[j]+=s[i];
k = max(k,j);
}
k++;
}
下面是装箱问题的解法：
void first_fit(float s[],int n,float c,float b[],int &k)
{
int i,j;
k =0; //装入物体的箱子下标
for(i=0;i<n;i++)
b[i] = 0; //箱子初始化为空
for(i=0;i<n;i++){ //按物体顺序装入
j = 0;
while((c-b[j])<s[i]) //检索能容纳物体i的校标最小的箱子j
j++;
b[j]+=s[i];
k = max(k,j);
}
k++;
}
#5
不过这个要比装箱复杂 在检索模板时模板的体积可能不是一个整体了。
因此可以将切割下来的原料都看做一个模板 然后再用最适宜算法进行类似装箱操作。
void first_fit(float s[],int n,float c,float LinkList L,int &k)
{
//用链表表示模板序列，方便添加和删除模板
int i;
Empty(L,c); //模板链表初始化
for(i=0;i <n;i++){ //按物体顺序装入
LinkList *p =L->next;
while(p){
.检索能容纳物体i的最小的模板节点p
.p->data-s[i]，这时模板节点p的data分为两个模板a,b
.创建新的模板节点:A->data = a;B->data = b;
.插入新模板 Insert(A);Insert(B);
}
}
}
因此可以将切割下来的原料都看做一个模板 然后再用最适宜算法进行类似装箱操作。
void first_fit(float s[],int n,float c,float LinkList L,int &k)
{
//用链表表示模板序列，方便添加和删除模板
int i;
Empty(L,c); //模板链表初始化
for(i=0;i <n;i++){ //按物体顺序装入
LinkList *p =L->next;
while(p){
.检索能容纳物体i的最小的模板节点p
.p->data-s[i]，这时模板节点p的data分为两个模板a,b
.创建新的模板节点:A->data = a;B->data = b;
.插入新模板 Insert(A);Insert(B);
}
}
}
#6
定义一个材料类，有长宽数量等属性
材料分为两类:原材料，目标材料。例如原材料 长9 宽9 数量9 目标材料:长7 宽5 数量 3 ；长 3 宽2 数量3
两种类型的材料都存到集合里面。
遍历原材料集合拿出一个材料。
再遍历目标材料集合。取最大的目标材料。进行切割。
原材料长减去目标材料长。原材料被分为两块。
原材料宽减去目标材料宽。原材料被分为三块。
处理完后，原材料分为两块可用。目标材料集合中数量减一
如果原材料的长宽不能被切割成最小的目标材料就废弃
分成的两块原材料有放入集合。迭代进行处理。直到原材料不能被处理。
依次进行处理直到所有原材料处理完
材料分为两类:原材料，目标材料。例如原材料 长9 宽9 数量9 目标材料:长7 宽5 数量 3 ；长 3 宽2 数量3
两种类型的材料都存到集合里面。
遍历原材料集合拿出一个材料。
再遍历目标材料集合。取最大的目标材料。进行切割。
原材料长减去目标材料长。原材料被分为两块。
原材料宽减去目标材料宽。原材料被分为三块。
处理完后，原材料分为两块可用。目标材料集合中数量减一
如果原材料的长宽不能被切割成最小的目标材料就废弃
分成的两块原材料有放入集合。迭代进行处理。直到原材料不能被处理。
依次进行处理直到所有原材料处理完
#7
数量不大的话，可以靠硬搜，数量大的话，还是找近似算法吧。应该属于NP级的。