数组的最小和分区

本文介绍了数组的最小和分区的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

问题陈述：

给出一个数组，任务是将其分为两组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