网易笔试：给出n个物品，每个物品都有自己的价值，每个物品只有一件，这些物品需要分给两个人，要求分配完之后，两个人的物品价值相同。分配完成之后，丢弃剩下的物品，求最少要丢弃多少物品。

桃扇骨 2022-11-25 11:57 148阅读 0赞

# 题目描述 #

给出n个物品，每个物品都有自己的价值，每个物品只有一件，这些物品需要分给两个人，要求分配完之后，两个人的物品价值相同。分配完成之后，会丢弃剩下的物品，求最少要丢弃多少物品。

## 输入 ##

输入第一行为总的测试数据个数，第二行为物品个数n，第三行为n个物品的价值。

## 输出 ##

最少要丢弃多少物品的价值总和。  
**示例：**  
输入：  
1  
5  
30 60 5 15 30  
输出：  
20 （丢弃5和15，把60分配给第一个人，2个30分配给第二个人。）

思路:  
dfs回溯  
C++实现

#include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    class Solution
    { 
    public:
    	int res = INT_MAX;
    	void dfs(vector<int> &nums, int index, int result1, int result2, int sum)
    	{ 
    		if (index == nums.size())
    		{ 
    			if (result1 == result2)
    				res = min(res, sum - 2 * result1);
    			return;
    		}
    		//分为3中情况，
    		/* 1. 谁都不给 2. 给第一个：result1 + nums[index] 3. 给第二个：result2 + nums[index] */
    		dfs(nums, index + 1, result1, result2, sum);
    		dfs(nums, index + 1, result1 + nums[index], result2, sum);
    		dfs(nums, index + 1, result1, result2 + nums[index], sum);
    	}
    };
    
    int main(void)
    { 
    
    	int sum = 0;
    	int group;
    	cin >> group;
    	Solution s;
    	
    	while (group-- > 0)
    	{ 
    		int n;
    		cin >> n;
    
    		vector<int> nums(n);
    		for (int i = 0; i < n; i++)
    		{ 
    			cin >> nums[i];
    			sum += nums[i];
    		}
    
    		s.dfs(nums, 0, 0, 0, sum);
    		cout << s.res;
    	}
    	return 0;
    }