首页 > 试题广场 >

平分物品

[编程题]平分物品

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

要求：时间复杂度 $O(3^n)$ ，空间复杂度 $O(n)$

第一行输入一个整数 T，代表有 T 组测试数据。
对于每一组测试数据，一行输入一个整数 n ，代表物品的个数。
接下来 n 个数，a[i] 代表每一个物品的价值。

1<= T <= 10
1 <= n <= 15
1 <= a[i] <= 100000

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

示例1

输入

1
5
30 60 5 15 30

样例解释，扔掉第三个和第四个物品，然后将第一个物品和第五个物品给第一个人，第二个物品给第二个人，每一个人分到的价值为 $60$ ，扔掉的价值为 $20$ 。

算法知识视频讲解

大厂算法岗必拿下

发表于 2021-09-17 04:11:48

转换成我们拿最大（二者相等）的时候，然后sum一减，就可以知道那个最小的剩余是多少。（在进行一次转换，取次次差得最小值）然后在转换成以每一个物品为基础，分为三种情况进行讨论。 #include<bits/stdc++.h> using namespace std; int res 展开全文

C++工程师运维工程师算法工程师网易测试开发工程师测试工程师游戏研发工程师 2021 大数据开发工程师 Java工程师

上传者：小小

难度：

20条回答 459收藏 8678浏览

扫一扫，把题目装进口袋