这个回溯算法，怎么添加输出最优路径

helian147

代码来源链接： https://blog.csdn.net/hhhmonkey/article/details/112972567

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

问题描述：
代码能运行，但希望能添加一个功能，将最优路径输出，代码如何修改？

[C++] 纯文本查看 复制代码

#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[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;
}

int main() {
    while(input()){
        solve(data,n);
        printf("\n%d\n",res);
    }
}