平分物品

[编程题]平分物品

热度指数：5581 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

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

算法知识视频讲解

Java

菲尼克斯弗兰克

第一反应是回溯+子集背包结果12/20 超时了，改成dfs排列组合就能过

import java.util.*;
public class Main {
    // 丢掉不需要的平分物品
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int i = 0; i < t; i++) {
            int n = in.nextInt();
            int[] arr = new int[n];
            sum = 0;
            for (int j = 0; j < n; j++) {
                arr[j] = in.nextInt();
                sum += arr[j];
            }
            min = Integer.MAX_VALUE;
            dfs(arr, 0, 0, 0, 0);
            System.out.println(min);
        }
    }
    // dfs排列组合-分给三个人
    static int min, sum;
    public static void dfs(int[] arr, int idx, int a, int b, int c) {
        if (a == b) {
            min = Math.min(min, sum-a-b);
        }
        for (int i = idx; i < arr.length; i++) {
            dfs(arr, i+1, a+arr[i], b, c);
            dfs(arr, i+1, a, b+arr[i], c);
            dfs(arr, i+1, a, b, c+arr[i]);
        }
    }
}

发表于 2022-08-24 14:59:02 回复(0)