413-回溯算法-2N整数选择问题-剪枝提升效率

我会带着你远行 2022-09-05 00:24 80阅读 0赞

**整数选择问题：给定2n个整数，从里面挑选出n个整数，让选择的整数的和，和剩下的整数的和的差最小**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]

int arr[] = {
         12,6,7,11,16,3,8,4 };
    const int length = sizeof(arr) / sizeof(arr[0]);
    vector<int> x;//记录子集中选择的元素
    vector<int> bestx;//记录最优解
    int sum = 0;//记录子集中所选数字的和
    int r = 0;//记录未选择数字的和
    unsigned int min = 0xFFFFFFFF;//记录最小差值
    int leftcnt = length;//记录未处理的数字的个数
    //int cnt = 0;//记录遍历的子集的个数，用于测试
    
    void func(int i)
    {
        
    	if (i == length)//到达叶子节点了
    	{
        
    		//cnt++;
    		//得到子集树的一个解，对应的是一个叶子节点
    		//x存储的是所选择的个数，如果小于全部数据的一半，不合题意
    		if (x.size() != length / 2)
    		{
        
    			return;//直接结束，因为这种解不满足题目要求
    		}
    
    		int result = abs(sum - r);
    		if (result < min)
    		{
        
    			min = result;
    			bestx = x;
    		}
    	}
    	else//还在深度遍历过程中，还没有到达叶子节点
    	{
        
    		leftcnt--;//表示处理i节点，表示剩余的未处理的元素的个数
    		if (x.size() < length / 2)//剪左树枝，提高算法效率。选择数字的前提：还未选择够n个整数
    		{
        
    			sum += arr[i];
    			r -= arr[i];
    			x.push_back(arr[i]);
    			func(i + 1);//遍历i的左孩子，表示选择i号位元素
    			sum -= arr[i];
    			r += arr[i];
    			x.pop_back();
    		}
    
    		//这里右树枝可以剪枝！ 已选择的数字的个数 + 未来能选择的所有的数字的个数(i+1,i+2....n) >= n个元素
    		//右树枝表示不选择，但是右孩子的左孩子可以被选。走右边是要能选够n个元素。
    		if (x.size() + leftcnt >= length / 2)
    		{
        
    			func(i + 1);//遍历i的右孩子，表示不选择i号位元素
    		}
    
    		//当前i节点已处理完成，回溯到其父节点了
    		leftcnt++;
    	}
    }
    int main()
    {
        
    	for (int v : arr)
    	{
        
    		r += v;
    	}
    	func(0);
    	for (int v : bestx)
    	{
        
    		cout << v << " ";
    	}
    	cout << endl;
    	cout << "min:" << min << endl;
    	//cout << "cnt:" << cnt << endl;
    	return 0;
    }

## 算法优化分析 ##

**如果不进行优化，我们用cnt变量测试一下**  
![在这里插入图片描述][5c26f3d97d9548cd97886bb7d0aa0f66.png]  
2^8=256，这个子集树有256个叶子节点，把所有的叶子节点全部都遍历了1遍！**但是题目给的条件**：2n个整数，从里面挑选出n个整数！  
选n+1个可以吗？不可以！  
选n-1个可以吗？不可以！  
![在这里插入图片描述][57805f32db5844aea8222cff6af65c0f.png]  
这样就不用去选择新的数字了！  
子集的个数已经超过n个了，就不用跑去叶子节点了，浪费算法效率了。

**优化方法：**  
**优化1：剪左树枝，提高算法效率。选择数字的前提：还未选择够n个整数**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][c27d732c94f64f4fb24a00381646f5cf.png]  
从256优化到163了。

**优化2：这里右树枝可以剪枝！ 已选择的数字的个数 + 未来能选择的所有的数字的个数(i+1,i+2…n) >= n个元素，才去当前节点的右子树走。如果小于n个元素，就不走右边去了。  
因为右树枝表示不选择，但是右孩子的左孩子可以被选。前提是走右边是要能选够n个元素，才去走。**  
未来能选择的所有的数字的个数表示：右孩子的未处理的个数。  
**因为每个元素都有选择和被选择两种情况，对应的是左右孩子节点。**

int leftcnt = length;//记录未处理的数字的个数，刚开始是一个都没有处理
    //所以初始化为数组的元素个数

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][d4a7e05c5e2c42f7b21215e191b8831a.png]  
**256-70了  
算法提高了3倍效率**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/083730f22b7e47d491be4e380fad2191.png
[5c26f3d97d9548cd97886bb7d0aa0f66.png]: /images/20220829/9fee4cdf056b4357a47f653327951737.png
[57805f32db5844aea8222cff6af65c0f.png]: /images/20220829/b1bd37cba4d8482986a1a5e489a68693.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/6c6439ea956b45f2b6d683780a67a5e7.png
[c27d732c94f64f4fb24a00381646f5cf.png]: /images/20220829/14bc668c5a7d45f2bc7bf60be8c0884c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/40a322a3dc3b48acb017a51dab6398d0.png
[d4a7e05c5e2c42f7b21215e191b8831a.png]: /images/20220829/01f53ff584b74836898e72d53ef00584.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/b4f76c15371e4b3eb824558f6f2673fc.png