钢材切割问题
最后更新于：2022-04-01 14:28:40
已知钢材的总长，订单数和各订单需要的长度编制程序从订单中选择一组订单对钢材作切割加工， 使得钢材得到最佳应用，约定，每次切割损耗固定长度的钢材。
下面写一下我的思路，刚开始没有想明白应该怎么使用递归去做，但是，看了他们的代码之后，走了一遍，才明白，其实思路不太好想，但是实现起来还是比较容易的。
假设，我们有一段钢材，长度为12米，其中有3个订单，分别需要的长度为5,6,9米，每次切割总会有2米的损耗，求得其最佳订单组合。
现在我们想想一下我们正常的思路：
如果是只有一个订单的话，9米的订单是最合适的，加上2米的耗材，一共11米。
如果有两个订单的话，有组合5,6；5,9；6,9这三个组合，很明显，这三个组合都已经超过了12米的长度，因为如果是5,6的话，虽然说订单的和为11，但是有两次切割，还会有4米的耗材，加起来就是15米，已经远远超过钢材的长度了
由上面的可以知道，3个订单的组合那就更不行了。
那我们应该如何做到实现这个思路呢，我们有一个数组记录订单是否选中，请看下面这张图：
5,6,9初始化的时候，全是未选中的状态，程序开始执行，先选中5，加上损耗的长度小于12，则继续选中6，这样加上损耗的长度大于12了，则设置6的状态为未选中；接着选中9,5加上9加上损耗的长度，很明显超过12了，那么设置9的状态为未选中；接着从5开始的遍历完成了，将5的状态设置为未选中；选中6，再从5开始选中，这样进行下去。。。。
当然，中间需要有两个变量记录最佳长度和最佳订单组合。
下面附上我的代码：
~~~
#include <stdio.h>
/**
* 已知钢材的总长，订单数和各订单需要的长度
* 编制程序从订单中选择一组订单对钢材作切割加工，
* 使得钢材得到最佳应用，约定，每次切割损耗
* 固定长度的钢材
*/
#define N 20
#define DELTA 2 //切割钢材损耗
/**最好的长度 **/
int bestlen;
/**最好长度的选定订单 **/
int bestsele[N];
/**选定订单，用于尝试选择 **/
int sele[N];
/**有n的订单 **/
int n;
/**订单需要的钢材的长度 **/
int orderlen[N];
/**钢材总长度 **/
int total;
void attempt();
int main(void)
{
int j;
//获取钢材的总长度
printf("Please enter the length of the steel:\n");
scanf("%d",&total);
//获取钢材的订单数
printf("Please enter the number of the orders:\n");
scanf("%d",&n);
//获取各个订单数需要的长度
printf("Please enter the length of every order:\n");
for(j = 0;j < n;j++)
scanf("%d",&orderlen[j]);
//初始化工作,使所有的订单都没有被选中
for(j = 0;j < n;j++)
bestsele[j] = sele[j] = 0;
//初始化最佳长度，设置为0
bestlen = 0;
//获取最佳长度
attempt();
printf("order:\n");
for(j = 0;j < n;j++){
if(bestsele[j])
printf("%d\t",orderlen[j]);
}
printf("\nlength:\n%d",bestlen);
return 0;
}
void attempt(){
int i,len;
//获取选中的订单的总长度（加上损耗）
for(len = i = 0;i < n;i++)
if(sele[i])
len += (orderlen[i]+DELTA);
if(len-DELTA <= total){ //注意，最后一个订单可能不需要损耗
if(bestlen < len){
bestlen = len;
for(i = 0;i < n;i++)
bestsele[i] = sele[i];
}
//每次尝试选择订单之后，需要将其还原未选中状态
for(i = 0;i < n;i++){
if(!sele[i]){
sele[i] = 1;
attempt();
sele[i] = 0;
}
}
}
}
~~~