数组的最小和分区 [英] Minimum sum partition of an array

问题描述

问题陈述：

给出一个数组，任务是将其分为两组S1和S2，以使它们之间的绝对差

Given an array, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.

样本输入，

[1,6,5,11] => 1 。这两个子集是 {1,5,6} 和 {11} ，总和为 12 和 11 。因此答案是 1 。

[1,6,5,11] => 1. The 2 subsets are {1,5,6} and {11} with sums being 12 and 11. Hence answer is 1.

[36,7,46,40] => 23 。这两个子集是 {7,46} 和 {36,40} ，总和为 53 和 76 。因此答案是 23 。

[36,7,46,40] => 23. The 2 subsets are {7,46} and {36,40} with sums being 53 and 76. Hence answer is 23.

约束

1 <=大小数组的< = 50

1 <= size of array <= 50

1< = a [i]< = 50

1 <= a[i] <= 50

我的努力：

int someFunction(int n, int *arr) {
    qsort(arr, n, sizeof(int), compare);// sorted it for simplicity
    int i, j;
    int dp[55][3000]; // sum of the array won't go beyond 3000 and size of array is less than or equal to 50(for the rows) 

    // initialize
    for (i = 0; i < 55; ++i) {
        for (j = 0; j < 3000; ++j)
            dp[i][j] = 0;
    }

    int sum = 0;
    for (i = 0; i < n; ++i)
        sum += arr[i];

    for (i = 0; i < n; ++i) {
        for (j = 0; j <= sum; ++j) {
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
            if (j >= arr[i])
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], arr[i] + dp[i][j + 1 - arr[i]]);
        }
    }

    for (i = 0; i < n; ++i) {
        for (j = 0; j <= sum; ++j)
            printf("%d ", dp[i + 1][j + 1]);
        printf("\n");
    }
    return 0;// irrelevant for now as I am yet to understand what to do next to get the minimum. 
}

输出

比方说输入 [1,5,6,11] ，我得到的是 dp 数组输出如下。

Let's say for input [1,5,6,11], I am getting the dp array output as below.

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 1 1 1 1 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 
0 1 1 1 1 5 6 7 7 7 7 11 12 12 12 12 12 12 12 12 12 12 12 12 
0 1 1 1 1 5 6 7 7 7 7 11 12 12 12 12 16 17 18 18 18 18 22 23 

现在，如何决定两个子集以获得最小值？

Now, how to decide the 2 subsets to get the minimum?

PS-我已经看过了链接，但是对于像我这样的DP初学者来说，解释还不够。

P.S - I have already seen this link but explanation is not good enough for a DP beginner like me.

推荐答案

您必须解决子集总和的问题，其中 SumValue = TotalSum / 2

You have to solve subset sum problem for SumValue = OverallSum / 2

请注意，您不需要解决任何优化问题（如使用 max

Note that you don't need to solve any optimization problem (as using max operation in your code reveals).

只需填充大小为（SumValue +的线性表（一维数组 A ） 1）使用可能的总和，获得最接近最后一个像元的非零结果（向后扫描A）wint索引 M 并将最终结果计算为 abs （OverallSum-M-M）。

Just fill linear table (1D array A) of size (SumValue + 1) with possible sums, get the closest to the last cell non-zero result (scan A backward) wint index M and calculate final result as abs(OverallSum - M - M).

要开始，将第0个条目设置为1。
然后每个源数组项目 D [i] 扫描数组 A 从头到尾：

To start, set 0-th entry to 1. Then for every source array item D[i] scan array A from the end to beginning:

A[0] = 1;
for (i = 0; i < D.Length(); i++)
  {
    for (j = SumValue; j >= D[i]; j--)  
      {
        if (A[j - D[i]] == 1)   
       // we can compose sum j from D[i] and previously made sum
             A[j] = 1;
       }
   }  

例如 D = [ 1,6,5,11] ，您有 SumValue = 12 ，使数组 A [13] ，并计算可能的总和

For example D = [1,6,5,11] you have SumValue = 12, make array A[13], and calculate possible sums

A array after filling: [0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1]

有效的Python代码：

working Python code:

def besthalf(d):
    s = sum(d)
    half = s // 2
    a = [1] + [0] * half
    for v in d:
        for j in range(half, v - 1, -1):
            if (a[j -v] == 1):
                a[j] = 1
    for j in range(half, 0, -1):
        if (a[j] == 1):
            m = j
            break
    return(s - 2 * m)

print(besthalf([1,5,6,11]))
print(besthalf([1,1,1,50]))
>>1
>>47

这篇关于数组的最小和分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！