一、题目描述
现在有n个物品，每一个物品都有一个价值，现在想将这些物品分给两个人，要求这两个人每一个人分到的物品的价值总和相同（个数可以不同，总价值相同即可），剩下的物品就需要扔掉，现在想知道最少需要扔多少价值的物品才能满足要求分给两个人。
要求：时间复杂度O ( 3 n ) O(3^n)O(3
n
)，空间复杂度O ( n ) O(n)O(n)
输入描述
第一行输入一个整数 T，代表有 T 组测试数据。 对于每一组测试数据，一行输入一个整数 n ，代表物品的个数。 接下来 n 个数，a[i] 代表每一个物品的价值。 1<= T <= 10 1 <= n <= 15 1 <= a[i] <= 100000
输出描述：
对于每一组测试数据，输出一个答案代表最少需要扔的价值。
测试用例：
输入： 1 5 30 60 5 15 30 输出：20 栗子说明：样例解释，扔掉第三个和第四个物品，然后将第一个物品和第五个物品给第一个人，第二个物品给第二个人，每一个人分到的价值为60，扔掉的价值为20。
二、解题思路
dfs遍历，每个节点的子结点中，有三种情况：给第一个人，给第二个人，丢掉。
几个变量说明：
n：需要选择的物品的总共数量。
sum：所有元素的总和。
全局变量res：找出满足情况的最值res，min(res, sum - result1 - result2)。
dfs的递归边界是遍历到最后一个元素，并且结束条件：搜索到最后一个物品时，判断res1和res2两者是否相等，如果相等则记录并更新res值。
三、C++代码
#include <iostream> #include<vector> #include<algorithm> #include<limits.h> using namespace std; // 最小扔掉的价值 int res = INT_MAX; void dfs(vector<int>& nums, int res1, int res2, int sum, int index, int n){ //一直选到最后一个数字才返回 if(index == n){ if(res1 == res2){ res = min(res, sum - res1 - res2); //res = sum - res1 - res2; } return; } // 每次的选择环节都有3种选择 dfs(nums, res1 + nums[index], res2, sum, index + 1, n); dfs(nums, res1, res2+ nums[index], sum, index + 1, n); dfs(nums, res1, res2, sum, index + 1, n); } int main (){ int t; cin >> t; // 组数 while(t--){ int n;//该组的物品总数 cin >> n; int temp; //当前存入值 vector<int> nums; for(int i =0; i < n ; i++){ cin >> temp; nums.push_back(temp); } // 计算该组的元素总和 int sum = 0; for(auto i : nums){ sum += i; } //vector，res1和res2和index初始都是0，sum需单独设变量存起来 dfs(nums, 0, 0, sum, 0, n); cout<<res<< endl; res = INT_MAX; } system("pause"); return 0; }
