回溯法子集树代码的感悟

不同于01背包类型的子集树，那个是只有一个背包，所以只会产生一个子集树，有用的终点为每一个物品都进行过是否放置的选择

这是一个一维选择问题，所以只会产生一个子集树

我们来看这个问题

某木匠在制作家具前往往需要将木料分割成长度不同的木块，在每次分割时会损坏一定长度的木头。现需制作某件家具，已知每块木料的长度，该家具制作时所需的木块的长度以及分割时损坏的木块的长度，请分析采用穷举法求解样例输入时的求解过程。

输入要求：输入1行，包含若干个整数，第1个整数是木料的长度，第2个整数为每次分割损坏的木块的长度，后面的整数则为该家具制作时所需的木块的长度。

输出要求：输出1个整数，即制作该家具所需的木料的块数。

样例输入：
1000 100 250 500 650 1000
样例输出：
3

首先讲讲我的想法，同样一个问题，我的想法是，通过进行切割木块的排序来遍历所有情况，木块编号：0，1，2，3。我可以排序为0123或者2130，或者1320，这种，然后每次切割的时候能用一块木料我就用一块木料，不能的话我再开新的木料。

解集空间如图

这种想法就极大的减少了解集空间，并且使其能够在一个树上呈现

而答案是另外一种有意思的想法

它设置了一个二维数组，a [ i ] [ j ] 表示第i个木料切出编号为j的木块，然后每一个行就是一个变形01背包问题这种的子集树，只是限制条件为能够切出来这个木块，而且能够不放满（能切但不切）的情况出现

然后在一个一维的每一种情况能够在递归生成新的树，这个树代表下一行，也就是下一个木块的分法，不过这个数的全集是目前还没分配好的木块。这个想法的函数特征是这样的

void func(int i,int j)
{
    operation;
    for(i;i<n;i++)
    {
        fun(0,j+1);
        fun(i,j);
    }
}

形式上是两个函数调用，其中fun(i,j);每个就是开枝散叶的本树，而fun(0,j+1)就是在调用下一颗树。

实现

这样子的功能

这时原本的树，但是这棵树的每一个节点就可以调用 fun(0,j+1)语句用来生成新的树

比如，我们这里的黄色3节点就又生成了

这棵树，这棵树的每一个节点又能生成Set[][]第三行的树，并且由于不同的节点可以生成不同的第三行的树，第三行的树也能够生成不同的第四行的树，所以这里是两个树复合在一起的算法

具体的解题思路和代码可以看这里回溯算法例题 · 郭帅/Misc - 码云 - 开源中国 (gitee.com)