看到这样一个题目:将一个数组分成两个子数组,使这两个数组的和的差值最小,并给出差值。

例子:
[3, 1, 5]应该分成[3, 1]和[5],因为这时两个数组和的差值为1。
[5, 9, 7, 2]应该分为[5, 7]和[9, 2],因为这时两个数组和的差值为1。

思路:
差值最小意思就是两个数组的和最接近,那两个分出来的数组的和都接近的是哪个值?
没错就是sum/2
假设用sum1表示第一部分的和,sum2表示第二部分的和,sum表示所有数的和,那么sum1+sum2=sum。
假设sum1<sum2 那么sum/2-sum1 = sum2-sum/2;
换句话说该题可以理解为:从一个数组里取出一些元素,使这些元素的和 <= sum/2。

其实这就是一个基础的01背包问题。参考链接
我们把背包的最大容量看成是sum/2。

状态方程为:

1
f[i][V] = max(f[i-1][V-v[i]]+v[i], f[i-1][V])

其中:
f[i][V]:表示用前i个物体装容量为V的背包能够装下的最大值.
f[i-1][V-v[i]]+v[i]:表示第i个物体装进背包的情况.
f[i-1][V]:表示第i件物品不装进背包的情况.

PHP代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
$arr = [3, 2, 5];
$n = count($arr);//物品总数
$v = array_sum($arr) / 2;//背包容量
$r = [];

for ($j = 0; $j <= $v; $j++) {
$r[0][$j] = $j >= $arr[0] ? $arr[0] : 0;
}
for ($i = 1; $i < $n; $i++) {//遍历物品
for ($j = 1; $j <= $v; $j++) {//遍历容量
$r[$i][$j] = $r[$i - 1][$j];//不放
if (($arr[$i] <= $j) && (($r[$i-1][$j - $arr[$i]] + $arr[$i]) > $r[$i][$j])) {//能放
$r[$i][$j] = $r[$i-1][$j - $arr[$i]] + $arr[$i];
}
}
}
echo 'two array min abs:' . (array_sum($arr) - 2 * $r[$n - 1][$v]);