部分總和永遠不會達到給定值的整數序列的排列

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。如果不是，則返回數組原樣的單個元素。 （END CASE）

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)