陣列分成兩個最接近集合問題

作者：Grey

原文地址：

部落格園：陣列分成兩個最接近集合問題

CSDN：陣列分成兩個最接近集合問題

問題描述

給定一個正數陣列 arr，請把 arr 中所有的數分成兩個集合，儘量讓兩個集合的累加和接近；

返回：最接近的情況下，較小集合的累加和。

主要思路

首先把陣列之和求出來，假設為 sum，那麼sum/2就是累加和的一半，定義遞迴函數

int process(int[] arr, int i, int rest)

遞迴含義表示：陣列 arr 從 i 開始，一直到最後，隨意選取進行累加，得到的最接近 rest 且較小的集合的累加和。

接下來是 base case，i 到陣列 arr 的結尾位置，顯然返回 0。

if (i == arr.length) {
    return 0;
}

接下來是普遍位置

        int p1 = process(arr, i + 1, rest);
        if (rest - arr[i] >= 0) {
            p1 = Math.max(process(arr, i + 1, rest - arr[i]) + arr[i], p1);
        }

其中 p1 表示：不選取 i 位置的值進行累加，得到的最接近 rest 且較小的集合的累加和。

process(arr, i + 1, rest - arr[i]) + arr[i]表示：選取了 i 位置的值進行累加，得到的最接近 rest 且較小的集合的累加和。

注：選取 i 位置的值進行累加有條件，即rest - arr[i] > 0，否則選取之後，會得到較大的那個集合的累加和。

遞迴方法的完整程式碼見（含對數器）


    public static int splitSumClosed(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        int aim = sum / 2;
        return process(arr, 0, aim);
    }

    public static int process(int[] arr, int i, int rest) {
        if (i == arr.length) {
            return 0;
        }
        int p1 = process(arr, i + 1, rest);
        if (rest - arr[i] >= 0) {
            p1 = Math.max(process(arr, i + 1, rest - arr[i]) + arr[i], p1);
        }
        return p1;
    }

以上暴力遞迴可以改成動態規劃，由於遞迴函數的可變引數有兩個，一個是 i，一個是 rest，且其變化範圍是固定的，所以可以定義一個二維陣列來存所有的遞迴過程值，

int[][] dp = new int[arr.length + 1][aim + 1];

接下來根據遞迴函數可知dp表的最後一行均為 0;

且dp[i][rest]依賴於dp[i+1][rest]和dp[i+1][rest - arr[i]]兩個位置的值，所以整個 dp 表可以從最後一行開始依次往上遞推。

      for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 0; j < aim + 1; j++) {
                int p1 = dp[i + 1][j];
                if (j - arr[i] >= 0) {
                    p1 = Math.max(dp[i + 1][j - arr[i]] + arr[i], p1);
                }
                dp[i][j] = p1;
            }
        }

動態規劃方法完整程式碼如下

    public static int splitSumClosed2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        int aim = sum / 2;
        int[][] dp = new int[arr.length + 1][aim + 1];
        // last row == 0
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 0; j < aim + 1; j++) {
                int p1 = dp[i + 1][j];
                if (j - arr[i] >= 0) {
                    p1 = Math.max(dp[i + 1][j - arr[i]] + arr[i], p1);
                }
                dp[i][j] = p1;
            }
        }
        return dp[0][aim];
    }

演演算法和資料結構筆記

陣列分成兩個最接近集合問題

陣列分成兩個最接近集合問題

問題描述

主要思路

更多