一个数组分成两个差值最小的子数组(01背包)

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

例子:
[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。

起始

Constant dropping wears the stone.