木材切割问题

雨点打透心脏的1/2处 2023-01-09 15:37 126阅读 0赞

## 木材切割问题 ##

一个木匠从木材公司买了一批木材，每块木材的长度均相同，但由于制作家具时所需的木块长度各不相同，因此需要把这些木材切割成长度不同的木块。同时每次切割时由于锯子本身有一定的宽度，因此每切割一次就会浪费掉一些木料。请设计一个程序使木匠能够用最少的木材切割出所需的木块。  
输入描述：  
输入有若干个测试样例，每个测试样例占一行。每行由若干个整数构成，第一个整数为所购买的木块的长度L（0<L<=30000）,第二个整数为锯子的宽度W（0<W<=1000）,其后的若干个整数分别表示制作家具时需要的木块的长度。  
输出描述：  
每个测试样例输出一行，为一个整数N，表示制作家具时需要购买的木块的数量。

样例输入：
    1000 100 250 250 500 650 1000
    1000 50 200 250 250 500 650 970
    样例输出：
    3
    4

代码如下：

#include<stdio.h>
    #include<malloc.h>
    #include<cstring>
    #define MAX_SAMPLE_LENGTH 50
    /*回溯法求解*/
    
    //是一个数组，将输入的木材尺寸保存至本数组
    int*data=(int*)malloc(MAX_SAMPLE_LENGTH*sizeof(int));
    //是一个布尔型数组，记录当前木料的当前切割方法中，第i个木材是否被切割出来
    bool*visited=(bool*)malloc(MAX_SAMPLE_LENGTH*sizeof(bool));
    //是一个布尔型数组，记录当前木料的最优切割方法中，第i个木材是否被切割出来
    bool*nVisited=(bool*)malloc(MAX_SAMPLE_LENGTH*sizeof(bool));
    //是一个布尔型数组，记录木材是否已经被之前的木料切割出来
    bool*res_arr=(bool*)malloc(MAX_SAMPLE_LENGTH*sizeof(bool)); 
    
    
    int w;//原材料长度
    int n;//数据元素个数
    int sw;//锯口宽度
    int cw;//当前已锯木头长度和
    int res;//求解结果
    int bestW;//当前求解最大值
    
    //获取输入的函数
    bool input(){ 
    	bool flag=true;
    	//初始化数据保存数组
    	memset(visited,false,MAX_SAMPLE_LENGTH*sizeof(bool));
    	memset(res_arr,false,MAX_SAMPLE_LENGTH*sizeof(bool));
    	memset(nVisited,false,MAX_SAMPLE_LENGTH*sizeof(bool));
    	//记录输入数据个数
    	n=0;
    	//读取数据-原材料(木头)长度
    	scanf("%d",&w);
    	if(0==w)flag=false;
    	//锯口宽度
    	scanf("%d",&sw);
    	while(flag){ 
    		scanf("%d",data+n);
    		n++;
    		char ch=getchar();
    		if(ch=='\n')break;
    	}
    	return flag;
    }
    
    //本函数用来计算每块木料的最优切割算法
    void backtrack(int i,int k){ 
    	//当当前木料已经把所有之前木料未切割出来的木材遍历完成，进入if
    	if(i>n-1){ 
    		//如果当前切割方法切割出来的木材总长度大于之前的最优解，进入if
    		if(bestW<cw){ 
    			//记录最优值
    			 bestW=cw;
    			//记录当前最优解
    			for(int i=0;i<n;i++){ 
    				nVisited[i]=visited[i];
    			}
    		}
    		return;
    	}
    	进入右子树条件：若当前木材尺寸未被之前的木料切割出来且当前木料还有空余量可以切割出当前尺寸
    	if(!res_arr[i]&&cw+data[i]+k*sw<=w){ 
    		//记录当前已锯木头数量
    		k++;
    		//进入右子树实际操作
    		cw+=data[i];
    		//访问标记
    		visited[i]=true;
    		//嵌套结构，计算data中下一个是否可在当前木料中被切割
    		backtrack(i+1,k);
    		//上一个树枝已经判断完了，退回上一个节点，抛弃上一种切割方法的最后一个节点，继续判断后面的木材是否可被切割。
            //假设共有5块木材需要被切割，即data[0]-data[4],若上一种情况可被切割的木材为data[0],data[1],data[2],此处抛弃data[2]，从这里 继续遍历，进行data[3]及之后的判断。
    		cw-=data[i];
    		k--;
    	}
    	visited[i]=false;
    	backtrack(i+1,k);
    }
    
    //本函数调用backtrack函数，用来计算需要多少块木料
    int solve(int*data,int n){ 
    	res=0;//求解结果初始化
    	int count=n;
    	// count剩余未锯木材数量,若存在未被切割的木材，则进入下一块木料的切割，while的每一次循环代表一块木料的切割。
    	while(count>0){ 
    		//初始化,cw当前已锯木头长度和,
    		//count剩余未锯木头数量,bestW本次求解最大长度和
    		cw=0,count=0,bestW=0;
    		//调用backtrack函数，计算每一块木料的最优解
    		backtrack(0,0);
    		for(int i=0;i<n;i++){ 
    			更新待解决问题状态：如果第i块木材未被之前的木料切割出，则将第i块木材是否被切割的状态更新为当前木料的切割情况。
    			if(!res_arr[i])
    				res_arr[i]=nVisited[i];
    			//计算剩余未切割出的木材的个数
    			if(!res_arr[i])
    				count++;
    		}
    		//记录求解结果
    		res++;
    	}
    	return res;
    }
    
    void main(){ 
    	while(input()){ 
    		solve(data,n);
    		printf("\n%d\n",res);
    	}
    }

附上该程序的debug视频，帮助理解整个运行过程：  
[https://www.bilibili.com/video/BV155411J7sz][https_www.bilibili.com_video_BV155411J7sz]

解空间树如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70]

[https_www.bilibili.com_video_BV155411J7sz]: https://www.bilibili.com/video/BV155411J7sz
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70]: /images/20221119/37657fccbe3e4f36b6015e867572e1ad.png