木材切割問題

一個(gè)木匠從木材公司買了一批木材，每塊木材的長度均相同，但由于制作家具時(shí)所需的木塊長度各不相同，因此需要把這些木材切割成長度不同的木塊。同時(shí)每次切割時(shí)由于鋸子本身有一定的寬度，因此每切割一次就會(huì)浪費(fèi)掉一些木料。請(qǐng)?jiān)O(shè)計(jì)一個(gè)程序使木匠能夠用最少的木材切割出所需的木塊。
輸入描述：
輸入有若干個(gè)測試樣例，每個(gè)測試樣例占一行。每行由若干個(gè)整數(shù)構(gòu)成，第一個(gè)整數(shù)為所購買的木塊的長度L（0<L<=30000）,第二個(gè)整數(shù)為鋸子的寬度W（0<W<=1000）,其后的若干個(gè)整數(shù)分別表示制作家具時(shí)需要的木塊的長度。
輸出描述：
每個(gè)測試樣例輸出一行，為一個(gè)整數(shù)N，表示制作家具時(shí)需要購買的木塊的數(shù)量。

樣例輸入： 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 /*回溯法求解*///是一個(gè)數(shù)組，將輸入的木材尺寸保存至本數(shù)組 int*data=(int*)malloc(MAX_SAMPLE_LENGTH*sizeof(int)); //是一個(gè)布爾型數(shù)組，記錄當(dāng)前木料的當(dāng)前切割方法中，第i個(gè)木材是否被切割出來 bool*visited=(bool*)malloc(MAX_SAMPLE_LENGTH*sizeof(bool)); //是一個(gè)布爾型數(shù)組，記錄當(dāng)前木料的最優(yōu)切割方法中，第i個(gè)木材是否被切割出來 bool*nVisited=(bool*)malloc(MAX_SAMPLE_LENGTH*sizeof(bool)); //是一個(gè)布爾型數(shù)組，記錄木材是否已經(jīng)被之前的木料切割出來 bool*res_arr=(bool*)malloc(MAX_SAMPLE_LENGTH*sizeof(bool)); int w;//原材料長度 int n;//數(shù)據(jù)元素個(gè)數(shù) int sw;//鋸口寬度 int cw;//當(dāng)前已鋸木頭長度和 int res;//求解結(jié)果 int bestW;//當(dāng)前求解最大值//獲取輸入的函數(shù) bool input(){bool flag=true;//初始化數(shù)據(jù)保存數(shù)組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));//記錄輸入數(shù)據(jù)個(gè)數(shù)n=0;//讀取數(shù)據(jù)-原材料(木頭)長度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; }//本函數(shù)用來計(jì)算每塊木料的最優(yōu)切割算法 void backtrack(int i,int k){//當(dāng)當(dāng)前木料已經(jīng)把所有之前木料未切割出來的木材遍歷完成，進(jìn)入ifif(i>n-1){//如果當(dāng)前切割方法切割出來的木材總長度大于之前的最優(yōu)解，進(jìn)入ifif(bestW<cw){//記錄最優(yōu)值bestW=cw;//記錄當(dāng)前最優(yōu)解for(int i=0;i<n;i++){nVisited[i]=visited[i];}}return;}進(jìn)入右子樹條件：若當(dāng)前木材尺寸未被之前的木料切割出來且當(dāng)前木料還有空余量可以切割出當(dāng)前尺寸if(!res_arr[i]&&cw+data[i]+k*sw<=w){//記錄當(dāng)前已鋸木頭數(shù)量k++;//進(jìn)入右子樹實(shí)際操作cw+=data[i];//訪問標(biāo)記visited[i]=true;//嵌套結(jié)構(gòu)，計(jì)算data中下一個(gè)是否可在當(dāng)前木料中被切割backtrack(i+1,k);//上一個(gè)樹枝已經(jīng)判斷完了，退回上一個(gè)節(jié)點(diǎn)，拋棄上一種切割方法的最后一個(gè)節(jié)點(diǎn)，繼續(xù)判斷后面的木材是否可被切割。//假設(shè)共有5塊木材需要被切割，即data[0]-data[4],若上一種情況可被切割的木材為data[0],data[1],data[2],此處拋棄data[2]，從這里 繼續(xù)遍歷，進(jìn)行data[3]及之后的判斷。cw-=data[i];k--;}visited[i]=false;backtrack(i+1,k); }//本函數(shù)調(diào)用backtrack函數(shù)，用來計(jì)算需要多少塊木料 int solve(int*data,int n){res=0;//求解結(jié)果初始化int count=n;// count剩余未鋸木材數(shù)量,若存在未被切割的木材，則進(jìn)入下一塊木料的切割，while的每一次循環(huán)代表一塊木料的切割。while(count>0){//初始化,cw當(dāng)前已鋸木頭長度和,//count剩余未鋸木頭數(shù)量,bestW本次求解最大長度和cw=0,count=0,bestW=0;//調(diào)用backtrack函數(shù)，計(jì)算每一塊木料的最優(yōu)解backtrack(0,0);for(int i=0;i<n;i++){更新待解決問題狀態(tài)：如果第i塊木材未被之前的木料切割出，則將第i塊木材是否被切割的狀態(tài)更新為當(dāng)前木料的切割情況。if(!res_arr[i])res_arr[i]=nVisited[i];//計(jì)算剩余未切割出的木材的個(gè)數(shù)if(!res_arr[i])count++;}//記錄求解結(jié)果res++;}return res; }void main(){while(input()){solve(data,n);printf("\n%d\n",res);} }

附上該程序的debug視頻，幫助理解整個(gè)運(yùn)行過程：
https://www.bilibili.com/video/BV155411J7sz

解空間樹如下圖：

總結(jié)

以上是生活随笔為你收集整理的木材切割问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。