1

我在面试时遇到了这个问题，似乎无法思考如何解决它。我还没有找到任何解释其背后逻辑的教程。

拥有函数ArrayChallenge(arr)，获取其中存储的整数数组，arr其中始终包含偶数个整数，并确定如何将它们拆分为两个偶数集，然后返回第一个集合的字符串表示形式，然后返回每个整数的第二个集合用逗号分隔，两组均按升序排序。首先出现的集合是第一个整数最小的集合。

例如如果 arr 是 [16,22,35,8,20,1,21,11]，那么你的程序应该输出 1,11,20,35,8,16,21,22

[16,22,35,8,20,1,21,11] 总和 = 134

1,11,20,35 之和 = 67 8,16,21,22 之和 = 67

两个数组的大小也等于 arr.length /2

4

3 回答 3

2

该问题不需要按时间顺序编码。制定一个集中程序来解决这个背包问题，但不要编写代码。然后对结果进行排序，并给出结果。

现在，如果您无法解决，例如超时，仍然有一种方法可以完成。

这个问题可以进一步简化，通过使用数组的arr和除以 2，然后搜索这个半和的子数组。

这个问题提出了一些奇怪的限制：arr保持偶数个值（8），两个结果数组应该有相同的偶数个值（都是 4）。

选择第 i个值属于哪个子数组是二进制的。

所以从一个排序数组开始，当达到一半时削减解决方案。

您可以从 00001111（位 1 的一半）开始，这可能太大了，以下位将是 00010111, 00011011, 00011101, 00011110, 00101110, ...

简单的递归可能更容易，最多计数一半：

// Array arr sorted decreasingly to have less values to try out.
boolean solve(Set<Integer> selectedNumbers, int selectedSum, int index) {
    if (selectedNumbers.size() >= arr.length/2) {
        return sum == arrSum/2;
    }
    if (index > arr.length) {
        return false;
    }
    boolean solved = false;

    // First case: add array element at this index:
    if (selectedSum + arr[index] <= arrSum/2) {
        seplectedNumbers.add(arr[index]);
        arrSum += arr[index];
        solved = solve(selectedNumbers, arrSum, index + 1);
        if (!solved) {
            // No remove(int index), so remove an Object, Integer.
            selectedNumbers.remove(Integer.valueOf(arr[index]));
            arrSum -= arr[index];
        }
    }

    // Second case: do not add array element at this index:
    if (!solved) {
        solved = solve(selectedNumbers, arrSum, index + 1);
    }
    return solved;
}

以上当然是蛮力解决方案。如果您从事运筹学，您可能会发现这些数字的分布（如提到的位）。但是需要时间，对我来说，我微薄的数学知识会阻止这种情况。解决后，如果您知道更快的解决方案，您可能会发表评论。

于 2021-10-18T11:24:54.827 回答
1

这个答案在精神上与Joop Eggen的答案相似。它实现了检查的（小）优化，selectedTotal 如果 discardedTotal超过目标则中止分支（请注意，这假设所有值都是正数；如果不是这种情况，并且最小值是，比如说x < 0，你会必须添加到所有值，运行算法，然后从答案中-x减去）。-x

输出与原始帖子所指定的完全相同 - 由于它仅在找到完整解决方案时生成，因此此代码应该比不断添加和从部分答案中删除值的算法更快，例如 Joop 的 (selectedNumbers.add后跟selectedNumbers.remove当事实证明不起作用时；设置操作可能很快，但不执行它们甚至更快！）。

public class Main {
    public static boolean search(int[] values, int goal, int index,
                                int selectedTotal, int discardedTotal,
                                List<Integer> selected, List<Integer> discarded) {
        if (selected.size() == values.length/2 &&
                discarded.size() == values.length/2) {
            return selectedTotal == goal;
        }
        if (selectedTotal > goal ||
                discardedTotal > goal ||
                index == values.length) {
            return selectedTotal == goal;
        }

        // try selecting value at index ...
        if (selected.size() < values.length/2 &&
                search(values, goal, index + 1,
                    selectedTotal + values[index], discardedTotal,
                    selected, discarded)) {
            selected.add(values[index]);
            return true;
        }

        // ... and, if that did not work, try discarding value at index
        if (discarded.size() < values.length/2 &&
                search(values, goal, index + 1,
                    selectedTotal, discardedTotal + values[index],
                    selected, discarded)) {
            discarded.add(values[index]);
            return true;
        }
        return false;
    }

    public static List<Integer> solve(int[] values) {
        Arrays.sort(values);
        int goal = IntStream.of(values).sum() / 2;
        List<Integer> selected = new ArrayList<>();
        List<Integer> discarded = new ArrayList<>();
        if ( ! search(values, goal, 0,
                0, 0, selected, discarded)) {
            throw new IllegalArgumentException("This puzzle cannot be solved");
        }
        Collections.reverse(selected);
        Collections.reverse(discarded);
        selected.addAll(discarded);
        return selected;
    }

    public static void main(String[] args) {
        System.out.println(solve(new int[] {16,22,35,8,20,1,21,11}));
    }
}
于 2021-10-18T17:12:40.753 回答
0

您将使用迭代并首先遍历数组。然后你做2个整数。在每个迭代周期中，您首先检查 integer1 是否大于 integer2。然后将一个数字放入 array1 并将其值添加到 integer1。重复。如果 int1 大于 int2，则将其放入 array2 并将值添加到 int2。最后，对数组进行排序，你就完成了。这就是我将如何解决它。这行得通吗？我真的很感兴趣。

于 2021-10-18T11:01:21.840 回答