一、题目描述
现在有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 栗子说明:样例解释,扔掉第三个和第四个物品,然后将第一个物品和第五个物品给第一个人,第二个物品给第二个人,每一个人分到的价
二、解题思路
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; }