文章目录

• 一、题目描述
• 二、解题思路
• 三、C++代码
• Reference

一、题目描述

现在有n个物品，每一个物品都有一个价值，现在想将这些物品分给两个人，要求这两个人每一个人分到的物品的价值总和相同（个数可以不同，总价值相同即可），剩下的物品就需要扔掉，现在想知道最少需要扔多少价值的物品才能满足要求分给两个人。

要求：时间复杂度 O ( 3 n ) O(3^n) O(3n)，空间复杂度 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;
}

Reference

https://www.nowcoder.com/question/next?pid=27972361&qid=1262805&tid=51115874