2023年8月1日发(作者：)

调整数组使差最⼩（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 11 48100 99 98 1 2 31 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> dp(n+1,vector(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 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>> dp(2n+1,vector(n+1,vector(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> dp(n+1,vector(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];

2023年8月1日发(作者：)

调整数组使差最⼩（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 11 48100 99 98 1 2 31 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> dp(n+1,vector(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 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>> dp(2n+1,vector(n+1,vector(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> dp(n+1,vector(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];