算法笔记 -搜索专题：深度优先搜索 （递归）01 背包问题_01背包递归树算法

解法一：未剪枝便于理解 满二叉树结构

解法二：剪枝

解法一：未剪枝便于理解 满二叉树结构

/*
    思路：
    - DFS函数 ：三个参数也是具有递归性质的 随地归层数的增加而不断改变的 ，各层堆栈之间的调用不是孤立的
    DFS(int index , int sumWeight, int sumValue) index 代表所能递归的最大层数 加上判断条件 （重量的限制）
    - 此处的递归开始条件不好确定 DFS(0, 0, 0) 如何确定开始index为0 而不是1？-1? 可以理解为下一个待选择的层数或元素 
        保证递归的连续性
        DFS函数的参数中必须记录当前处理的物品编号 index 因此也需要参数来记录在处理当前物品之前,已选物品的总重量sumW与总价值sumC。于是DFS函数看起来是这个样子:
	
	void DFS(int index;int sumW,int sumc){……} 
	
    - 重要变量 递归过程中也得使用的变量 都放在全局位置 


*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int count = 0;
const int maxn = 10;
int weight[maxn], value[maxn];
int bagCapacity, stuffNums, maxValue = 0;
void DFS(int index, int sumWeight, int sumValue) {
   
    //递归边界
    count++;
    if (index == stuffNums) {
   
        //注意 stuffNums开始是从0开始的 所以这里的边界是 index = sstuffNums 如果还能跑到这一层并且背包还没满就给全局变量maxValue赋值
        if (sumWeight <= bagCapacity && sumValue > maxValue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29