java - 部分和永远不会达到给定值的整数序列的排列

Question

我一直在想办法解决这个问题，但无济于事。我有两个输入数组:a[n] 和 b[n-1]。我想要做的是输出数组“a”的排列，使得没有部分和等于数组“b”中的任何元素。我将尝试用一个例子来说明这一点:

a = {1, 3, 7}

b = {4, 8}

因此，在这种情况下，置换 {1, 3, 7} 不起作用，因为我们有部分和:

1, 1 + 3 = 4(数组 b 的一部分)，1 + 3 + 7 = 11。

一个好的排列是 {3, 7, 1}，因为我们有部分和:

3, 3 + 7 = 10, 3 + 7 + 1 = 11(结果不在数组 b 中)。

我尝试过动态规划的方法(主要是子集求和问题)，但在这种情况下似乎没有用。有人知道如何解决这个问题吗？

Answer 1

我建议的算法是递归的，我还有一个可能有用的代码示例。这个想法是相反的:

首先看数组a的总和是否出现在数组b中(如果是，我们就此打住)。

一旦我们清除了总和检查，我们就需要决定元素的顺序。我们从最后开始，为最后一个位置选择一个候选 i，看看我们是否可以对 n-1 数组 a 重复这个过程，其中我们删除了我们的来自数组的候选者。如果我们这样做，我们将候选 i 添加到返回数组的末尾位置 - 然后返回该数组。

递归步骤是:

1. 给定一个数组，检查它是否只包含一个元素。如果是，则检查该元素是否存在于禁止和数组中，如果是，则返回 null。如果不是，则按原样返回包含单个元素的数组。 (结束案例)

2. 给定一个包含多个元素的数组:

   2.1。检查它的总和与禁止的总和数组。如果存在，则返回 null。如果不是，则遍历数组并针对每个元素 i 递归调用该方法，并使用没有候选 i 的数组。

   2.2。如果递归调用返回 null - 继续迭代。

   2.3。如果它返回一个数组，则将元素 i 附加到数组的末尾并返回它。

下面的代码显示了 Java 中的算法。我尽量保持简单。

public static boolean contains(int[] arr, int val) {

    for (int i : arr) {
      if (i == val) {
        return true;
      }
    }
    return false;
  }

  public static int sum(int[] arr) {

    int sum = 0;
    for (int i : arr) {
      sum += i;
    }
    return sum;
  }

  public static int[] removeElem(int index, int[] arr) {

    int[] retArr = new int[arr.length - 1];
    for (int i = 0; i < index; i++) {
      retArr[i] = arr[i];
    }
    for (int i = index + 1; i < arr.length; i++) {
      retArr[i - 1] = arr[i];
    }
    return retArr;
  }

  public static int[] getArr(int[] arr, int[] forbidden) {

    if (arr.length == 1) {
      if (!contains(forbidden, arr[0]))
        return arr;
      else
        return null;
    }
    else {
      if (contains(forbidden, sum(arr))) {
        return null;
      }
      else {
        for (int i = 0; i < arr.length; i++) {
          int[] retArr = getArr(removeElem(i, arr), forbidden);
          if (retArr != null) {
            int[] newArr = new int[arr.length];
            for (int j = 0; j < retArr.length; j++) {
              newArr[j] = retArr[j];
            }
            newArr[newArr.length - 1] = arr[i];
            return newArr;
          }
        }
      }
    }
    return null;
  }

  public static void main(String[] args) throws IOException {

    int[] a = { 1, 3, 7, 9 };
    int[] b = { 4, 19, 16 };

    System.out.println("input array a: " + Arrays.toString(a));
    System.out.println("forbidden sum array b: " + Arrays.toString(b));
    System.out.println(Arrays.toString(getArr(a, b)));
  }

输出:

input array a: [1, 3, 7, 9]
forbidden sum array b: [4, 19, 16]
[9, 1, 7, 3]

再举几个例子:

input array a: [1, 3, 7, 9]
forbidden sum array b: [4, 19, 8]
[9, 7, 1, 3]

input array a: [1, 3, 7, 9]
forbidden sum array b: [4, 10, 8]
[9, 7, 3, 1]

input array a: [1, 3, 7, 9]
forbidden sum array b: [4, 10, 20]
null 
(for impossible forbidden sum)