调整数组使差最小 （01背包问题变形）（一个数组分成同大小部分或一个数组分成不同大小两部分）
最近看到两道背包问题变形的题目，形式很相似，做个总结。
01背包问题：在n个物体中向容量为V的背包中放，第i个物体的体积为C[i],其价值为W[i]，如何选取使得背包中的物体总价值最大。（注意i是从1开始）
问题1：将数组分为两部分，不要求两部分元素个数一致，使得两部分的和最接近，返回两部分的差值。例如：
int[] array={1,0,1,7,2,4}，分为两部分为{1,0,1,2,4}，{7}，差值为1。
思路：两部分和最接近，那么两部分的和尽量向sum(array)/2靠拢。也就是从array中选取若干个元素，使得选取的元素和尽量靠近sum(array)/2。
抽象成背包问题为：在n个物体中向容量为sum(array)/2的背包中放东西，每个东西的体积为array[i],价值为array[i]，如何选取物体使得背包中的总价值最大。
有人就问了，让背包中的总价值最大，超过了sum(array)/2怎么办？
仔细想想就知道不会如此了，因为有V=sum(array)/2控制着，放了体积多大的东西，就贡献了多大的价值，体积是无法超过sum(array)/2，那么总价值也不会超过sum(array)/2。所以抽象背包问题的实际含义为如何选取物体使得物体中的总价值最接近sum(array)/2。
状态转移方程和01背包的状态转移方程一样：
dp[i][v]的意思便是前i个元素放入容量为v的背包中的最大价值。
dp[n][sum(array)/2] 便是其中一个部分的和，两个部分之间的差为 sum(array) - 2*dp[n][sum(array)/2]
观察到转移方程的右边dp的第一个维度都是i-1，我们可以考虑压缩空间，也就是利用滚动数组进行优化空间，优化后的状态转移方程为：
这时dp[v]可以理解为容量是v的背包可以获得的最大价值
问题2：
Description
有两个序列 a,b，大小都为 n,序列元素的值任意整数，无序； 要求：通过交换 a,b 中的元素，使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。
Input
输入第一行为用例个数， 每个测试用例输入为两行，分别为两个数组，每个值用空格隔开。
Output
输出变化之后的两个数组内元素和的差绝对值。
Sample Input 1 Sample Output 1
1 48
100 99 98 1 2 3
1 2 3 4 5 40
思路：这题相对于上一题变化更大。我们假设a,b两个序列是一个序列array，那么问题就是将序列array划分为元素个数相同的两个部分，且两个部分之间的差最小。也就是从2n个数中选取n个数，使得选取的数的和尽量靠近sum(array)/2。（c是合并之后的序列）
抽象成背包问题为：从2n个物体中选取n个物体，将n个物体放入体积为sum(array)/2的背包中，物体体积为c[i]，价值为c[i]，如何选取这n个物体使得选取的物体总价值最大。
这个问题相对于上一个问题多了一个条件：选取的物体数量必须是总数量的一半。
我们可以将物体数量看作物体的另一个费用维度，现在的物体的费用也就是个数和体积两个维度。再次阐述问题为：从2n个物体中选取若干个物体，将物体放入体积为sum(array)/2且只能容纳n个物体的背包中，物体i体积为c[i]，个数为1（定值），价值为c[i]，如何选取物体使得选取的物体总价值最大。
状态转移方程：
dp[i][j][v]表示在前i个物体中将j个物体放入到容量为v的背包中所获得的最大价值。其中dp[2n][n][sum(array)/2]便是其中一个划分部分的和。
同样可以用滚动数组优化：
dp[j][v]表示在容量为v的背包中，最多选 j 件时可以得到的最大价值。
代码：
tips：优化后的代码和未优化后的代码的区别、代码中用的是array[i-1]、最外层循环起始值
问题1 方程1 代码：
vector<vector<int>> dp(n+1,vector<int>(sum(array)/2+1,0));
for(int i=1;i<=n;i++)//注意i的始末值
{
for(int v=array[i-1];v<=sum(array)/2;v++)
{
dp[i][v] = max(dp[i-1][v],dp[i-1][v-array[i-1]]+array[i-1]);
}
}
int sumofpart = dp[n][sum(array)/2];
问题1 方程2 代码：
vector<int> dp(sum(array)/2+1,0);
for(int i=1;i<=n;i++)
{
for(int v=sum(array)/2;v>=array[i-1];v--)//注意v的始末值
{
dp[v] = max(dp[v],dp[v-array[i-1]]+array[i-1]);
}
}
int sumofpart = dp[sum(array)/2];
问题2 方程1 代码：
vector<vector<vector<int>>> dp(2n+1,vector<int>(n+1,vector<int>(sum(array)/2+1,0)));
for(int i=1;i<=2n;i++)
{
for(int j=1;j<=n;j++)
{
for(int v=array[i-1];v<=sum(array)/2;v++)
{
dp[i][j][v] = max(dp[i-1][j][v],dp[i-1][j-1][v-array[i-1]]+array[i-1]);
}
}
}
int sumofpart=dp[2n][n][sum(array)/2];
问题2 方程2 代码：
vector<vector<int>> dp(n+1,vector<int>(sum(array)/2+1,0));
for(int i=1;i<=2n;i++)
{
for(int j=n;j>=1;j--)//注意j的始末值
{
for(int v=sum(array);v>=array[i-1];v--)//注意v的始末值
{
dp[j][v] = max(dp[j][v],dp[j-1][v-array[i-1]]+array[i-1]);
}
}
}
int sumofpart=dp[n][sum(array)/2];