数组划分为两个差值最小的数组

发表于

输入

一个数组arr

输出

arr划分出的两个子数组sub1和sub2,使这两个数组的和的差的绝对值最小,输出最小的差

思路

01背包问题,使背包中的总数最接近上限,即原数组的和的一半,最后的差值为背包空余空间的两倍.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function divide(arr){
    let len = arr.length
    let sum = 0;
    for(let i =0; i<len; i++)
        sum += arr[i]

    var dp = [];
    for(let i =0; i<=len ; i++){
        let tmp = []
        for(let j =0; j<=sum/2; j++){
            tmp.push(0)
        }
        dp.push(tmp)
    }

    for(let i =1; i<=len; i++){
        for(let j =1; j<=sum/2; j++){
            if(j>=arr[i-1])
                dp[i][j] = Math.max(dp[i-1][j-arr[i-1]]+arr[i-1])
            else
                dp[i][j] = dp[i-1][j]
        }
    }
    return sum - 2*dp[len][sum/2]
}
var arr = [1,2,3,4,5,6,7,8,9,10,999]
console.log(divide(arr))

结果

结果