这个回溯算法，怎么添加输出最优路径
代码来源链接： https://blog.csdn.net/hhhmonkey/article/details/112972567木材切割问题
一个木匠从木材公司买了一批木材，每块木材的长度均相同，但由于制作家具时所需的木块长度各不相同，因此需要把这些木材切割成长度不同的木块。同时每次切割时由于锯子本身有一定的宽度，因此每切割一次就会浪费掉一些木料。请设计一个程序使木匠能够用最少的木材切割出所需的木块。
输入描述：
输入有若干个测试样例，每个测试样例占一行。每行由若干个整数构成，第一个整数为所购买的木块的长度L（0<L<=30000）,第二个整数为锯子的宽度W（0<W<=1000）,其后的若干个整数分别表示制作家具时需要的木块的长度。
输出描述：
每个测试样例输出一行，为一个整数N，表示制作家具时需要购买的木块的数量。
问题描述：
代码能运行，但希望能添加一个功能，将最优路径输出，代码如何修改？
#include<stdio.h>
#include<malloc.h>
#include<cstring>
#define MAX_SAMPLE_LENGTH 500
/*回溯法求解*/
//数组，输入的木材尺寸保存至数组
int*data=(int*)malloc(MAX_SAMPLE_LENGTH*sizeof(int));
//数组，输出结果
int*data_res =(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;
//读取数据: 原材料(木头)长度 w
scanf("%d",&w);
if(0==w) flag=false;
//读取数据: 锯口宽度 sw
scanf("%d",&sw);
//读取数据: 要求切割的长度 data，此时开始 n++
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
// cw当前已锯木头长度和,bestW本次求解最大长度和
if(bestW<cw){
//记录最优值
bestW=cw;
//记录当前最优解
for(int i=0;i<n;i++){
nVisited=visited;
}
}
return;
}
//进入右子树条件：若当前木材尺寸未被之前的木料切割出来, 且当前木料还有空余量可以切割出当前尺寸
if(!res_arr&&cw+data+k*sw<=w){
//记录当前已锯木头数量
k++;
//进入右子树实际操作
cw+=data;
//访问标记
visited=true;
//嵌套结构，计算data中下一个是否可在当前木料中被切割
backtrack(i+1,k);
//上一个树枝已经判断完了，退回上一个节点，抛弃上一种切割方法的最后一个节点，继续判断后面的木材是否可被切割。
//假设共有5块木材需要被切割，即data-data,
//若上一种情况可被切割的木材为data,data,data,此处抛弃data，
//从这里 继续遍历，进行data及之后的判断。
cw-=data;
k--;
}
visited=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)
res_arr=nVisited;
//计算剩余未切割出的木材的个数
if(!res_arr){
count++;
}
}
//记录求解结果
res++;
}
return res;
}
int main() {
while(input()){
solve(data,n);
printf("\n%d\n",res);
}
}
页:
[1]