平分物品 笔试题练习小结

题目链接：https://www.nowcoder.com/test/question/908255677b6f4c18a9074c12f21acd59?pid=27972467&tid=56290657

题目

现在有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

输出例子1:
20

例子说明1:
样例解释，扔掉第三个和第四个物品，然后将第一个物品和第五个物品给第一个人，第二个物品给第二个人，每一个人分到的价值为，扔掉的价值为。
  

代码

Python版

T = int(input()) #取出循环组数
for x in range(T):
    n = int(input()) #取出一组内数字个数
    a = list(map(int,input().split())) #遍历数组保存至list
    ans = 10000000000
    def DFS(x, n, A, B, C):
        global ans
        if C > ans:return #递归终止条件
        if x>=n:
            if A == B:
                ans = min(ans,C) #取C的最小值
            return
        DFS(x+1,n,A+a[x],B,C)
        DFS(x+1,n,A,B+a[x],C)
        DFS(x+1,n,A,B,C+a[x])
    DFS(0, n, 0, 0, 0)
    print(ans)
   

Java版：

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static int min = Integer.MAX_VALUE;
	public static void  dfs(int[] list,int i,int A,int B,int C) {
		
        if(i>=list.length) {
			if(A==B) {
				min = Math.min(min, C);
			}
			//System.out.println("A"+A+" B"+B+" C"+C);
			return;
		}
		
		dfs(list,i+1,A+list[i], B, C);
		dfs(list,i+1,A, B+list[i], C);
		dfs(list,i+1,A, B, C+list[i]);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		int nums = scanner.nextInt(); //轮数
		for(int i=0;i<nums;i++) {
			int n = scanner.nextInt(); //一轮的数字个数

			scanner.nextLine();
			int[] list = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

			dfs(list, 0, 0, 0, 0);
			System.out.println(min);
            min = Integer.MAX_VALUE;
		}
		
	}

}