快捷搜索:  朋友圈  as  伪静态  次数  响应式  虎牙  浏览数  anniu

【网易算法提前批】平分物品

文章目录

一、题目描述二、解题思路三、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  101  n  151  a[i]  100000

输出描述

对于每一组测试数据输出一个答案代表最少需要扔的价值。

测试用例

输入1530 60 5 15 30输出20栗子说明样例解释扔掉第三个和第四个物品然后将第一个物品和第五个物品给第一个人第二个物品给第二个人每一个人分到的价值为60扔掉的价值为20。

二、解题思路

dfs遍历每个节点的子结点中有三种情况给第一个人给第二个人丢掉。

几个变量说明
n需要选择的物品的总共数量。
sum所有元素的总和。
全局变量res找出满足情况的最值resmin(res, sum - result1 - result2)

您可能还会对下面的文章感兴趣: