412-回溯算法-整数选择问题求解

﹏ヽ暗。殇╰゛Y 2022-09-05 00:22 182阅读 0赞

**整数选择问题：给定一组整数，从里面挑选出一组整数，让选择的整数的和，和剩下的整数的和 的差 最小**

## 解题思想 ##

**我们使用子集树来求解，我们把所有可能产生的子集都罗列一遍，和剩下的数字做个差值，比较出最小的。**

**写法1：**

int arr[] = {
         12,6,7,11,16,3,8 };
    const int length = sizeof(arr) / sizeof(arr[0]);
    int x[length] = {
         0 };//子集树辅助数组 记录节点走向左孩子还是右孩子，代表i节点被选择&未被选择
    int bestx[length] = {
         0 };//记录最优解
    unsigned int min = 0xFFFFFFFF;//记录最小的差值
    int sum = 0;//计算所选子集数字的总和
    int r = 0;//记录未选择数字的和
    
    //生成子集树
    / void func(int i)
    {
        
    	if (i == length)//访问到了子集树的一个叶子节点
    	{
        
    		//计算sum   
    		int result = abs(sum - r);//计算差值的绝对值
    		if (result < min)
    		{
        
    			min = result;
    			//需要记录一下差值最小的子集
    			for (int j = 0; j < length; ++j)
    			{
        
    				bestx[j] = x[j];
    			}
    		}
    	}
    	else
    	{
        
    		r -= arr[i];//减掉选择的
    		sum += arr[i];
    		x[i] = 1;
    		func(i + 1);//选择i节点
    		sum -= arr[i];//状态回退
    		r += arr[i];//算回去
    
    		x[i] = 0;
    		func(i + 1);//不选择i节点
    	}
    }
    
    int main()
    {
        
    	for (int v : arr)
    	{
        
    		r += v;
    	}//算出总和
    	func(0);
    	for (int i = 0; i < length; ++i)
    	{
        
    		if (bestx[i] == 1)
    		{
        
    			cout << arr[i] << " ";
    		}
    	}
    	return 0;
    }

![在这里插入图片描述][a3fd80d28796426a8defc722f93f6a7b.png]

**写法2：**

int arr[] = {
         12,6,7,11,16,3,8 };
    const int length = sizeof(arr) / sizeof(arr[0]);
    //int x[length] = { 0 };//子集树辅助数组  记录节点走向左孩子还是右孩子，代表i节点被选择&未被选择
    //int bestx[length] = { 0 };//记录最优解
    vector<int> x;
    vector<int> bestx;
    unsigned int min = 0xFFFFFFFF;//记录最小的差值
    int sum = 0;//记录所选子集数字的总和
    int r = 0;//记录未选择数字的和
    
    //生成子集树
    void func(int i)
    {
        
    	if (i == length)//访问到了子集树的一个叶子节点
    	{
        
    		//sum   
    		int result = abs(sum - r);
    		if (result < min)
    		{
        
    			min = result;
    			//需要记录一下差值最小的子集
    			bestx = x;
    		}
    	}
    	else
    	{
        
    		r -= arr[i];
    		sum += arr[i];
    		x.push_back(arr[i]);
    		func(i + 1);//选择i节点
    		sum -= arr[i];
    		r += arr[i];
    
    		x.pop_back();
    		func(i + 1);//不选择i节点
    	}
    }
    
    
    int main()
    {
        
    	for (int v : arr)
    	{
        
    		r += v;
    	}
    	func(0);
    
    	for (int v : bestx)
    	{
        
    		cout << v << " ";
    	}
    	cout << endl;
    	cout << "min:" << min << endl;
    	return 0;
    }

[a3fd80d28796426a8defc722f93f6a7b.png]: /images/20220829/6bad0115d4cd499f90f1b8120c93d67d.png