2個非連續相等子陣列之間的最小絕對差異

注：我知道這裏已經提出了這個問題，但是我沒有正確理解解決方案，並且我沒有足夠的評論來澄清我的查詢。（我是SO的初學者）2個非連續相等子陣列之間的最小絕對差異

問題：給定一個大小爲n的數組，將數組分成2個大小爲n/2的非連續子數組（n爲偶數），n -1）/ 2 &（n + 1）/ 2（如果n是奇數），使得2個子陣列之和的絕對差最小。

例子：

4 5 3 55 -3 23 3 20 100 90

回答：0 說明：{100, 20, 23, 4, 3}和{5, 55, -3, 3, 90}，兩者之和爲150

的我知道貪婪的做法不會爲這方面的工作，並認爲這涉及動態編程。但是，我無法建立一個解決方案來確保所考慮的子陣列大小相同，我的解決方案會生成任意大小的最小差分子陣列，這是一個常見的分區問題。

我也不確定製作表是否是一個好主意，因爲數字可能很大。（雖然它確定所有輸入都在int的範圍內）。

任何人都可以提供我可以應用的算法嗎？

這裏是鏈接到這個問題已經被問（回答）：Dividing an array into two subsets of equal sizes having minimum difference in sum of values.

來源

2016-08-05 Utkarsh

請提供原始問題的鏈接。 – MrSmith42

@ MrSmith42我已經在問題中提供了鏈接。 – Utkarsh

遞歸實現（JAVA）：

private static long minimalDiff(int[] nums, int sumA, int sumB, int indexA, int indexB) { 
    int index = indexA + indexB + 2; 
    if (index == nums.length) { 
     return Math.abs(sumA - sumB); 
    } else if (Math.max(indexA, indexB) * 2 > nums.length - 1) { 
     return Integer.MAX_VALUE; 
    } else if (Math.abs(sumA + nums[index] - sumB) < Math.abs(sumB + nums[index] - sumA)){ 
     long result = minimalDiff(nums, sumA + nums[index], sumB, indexA + 1, indexB); 
     if (result > 0) { 
      result = Math.min(result, minimalDiff(nums, sumB + nums[index], sumA, indexB + 1, indexA)); 
     } 
     return result; 
    } else { 
     long result = minimalDiff(nums, sumB + nums[index], sumA, indexB + 1, indexA); 
     if (result > 0) { 
      result = Math.min(result, minimalDiff(nums, sumA + nums[index], sumB, indexA + 1, indexB)); 
     } 
     return result; 
    } 
} 

public static long minimalDiff(int[] num) { 
    if (num == null || num.length < 2){ 
     throw new IllegalArgumentException("num"); 
    } 
    return minimalDiff(num, 0, 0, -1, -1); 
} 

public static void main(String[] args) { 
    int [] test= {4, 5, 3, 55, -3, 23, 3, 20, 100, 90}; 
    System.out.println("Answer: "+minimalDiff(test)); 
}

它打印：

Answer: 0

來源

2016-08-05 16:54:08

2個非連續相等子陣列之間的最小絕對差異

回答

相關問題