c - 数组的最小和分区

Question

问题陈述:

给定一个数组，任务是将它分成两个集合 S1 和 S2，使得它们和之间的绝对差值最小。

示例输入，

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

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

约束

1 <= size of array <= 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 数组输出。

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 

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

P.S - 我已经看过这个 link但对于像我这样的 DP 初学者来说，解释还不够好。

Answer 1

您必须解决 SumValue = OverallSum/2 的 subset sum 问题

请注意，您不需要解决任何优化问题(因为在您的代码中使用 max 操作显示)。

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

首先，将第 0 个条目设置为 1。 然后对于每个源数组项 D[i] 从末尾到开头扫描数组 A:

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]，并计算可能的总和

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

工作的 Python 代码:

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