个人简介
小公司研发总监，既当司令也当兵！
文章分类
相关博文
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
分类： linux
2016-11-20 21:35:20
题目
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];
交换后
a=[100, 40, 5, 4, 3, 3]
b=[99, 98, 2,2, 1, 1]
分析
1. 网上有思路采用 贪婪算法
大意为：
当前数组a与数组b的各自累加和的差为
a = sum(a) - sum(b)
假设数组a的i元素与数组b的j元素互换，新的a数组与b数组各自累加和的差为
a' = sum(a) b[j] - a[i] - ( sum(b) a[i] - b[j])
= sum(a) - sum(b) - 2*(a[i] - b[j])
= a - 2* (a[i] - b[j])
假设a大于0， 那么如果能够找到这样的a[i] 与b[j], 使得 |a[i] - b[j]| 在（0，a）之间，那么交换这两个元素，数组a与数组b累加和之间的差值将变小。
据此可以得出算法
（1）计算数组a与数组b累加和差值，记为a；
（2）在数组a与b之间选择这样一组元素，它们的差值比a小；
（3）交换这组元素；
（4）重复（1），（2），（3）步，直到找不到合适的元素组即完成。
网上有类似的算法，本文就不贴代码了。
上面的算法是一个典型的贪心算法，能够得到局部最优解，但未必能够得到全局最优。http://blog.csdn.net/cwqbuptcwqbupt/article/details/7521733， 对此作了反例。
2. 重新分析：
题目的一个等价命题为，给定2n个元素，累加和为sum，从中选择n个元素，使得选择的n个元素的累加和尽量接近sum/2 。
经过这样命题转换，我们把两个数组统筹在一起了，更有全局观了（废话）。这样从一堆物品中选择出一堆且满足一定要求，首先联想到背包问题。那么能不能转换为背包问题求解呢？
考虑
我们有一个背包容量为sum/2的背包，给定物品有2n个，第i个物品的重量为w[i]，要求装入物品的个数恰好为n，且总重量尽量接近sum/2。
上面定义转换为了一个背包问题，但又与常见的01背包问题有差别。事实上，该背包有两个限制：其一是物品个数，其二是物品总重量。
那么我们为每个元素定义两个属性：其一，重量属性，其二，数量属性（或体积属性）。
那么我们的“物品”和“背包”：
有2n个物品，第i个物品体积为c[i] (均为1）, 重量为w[i]。现有一个背包， 背包体积容量为n， 承重为w。如何选择物品装入背包中，使得背包恰好装满（体积），物品总重量不超过背包承重，且总重量达到最大？
由于物品重量既是限制又是目标，稍微有点混乱，我们再引入一个物品属性：价值（不过，凑巧的是物品价值和物品质量是相等的）。再定义如下：
有2n个物品，物品i 的体积为c[i] (均为1）， 重量为 w[i], 价值为v[i] (v[i] = w[i])。现有一个背包，背包体积容量为n，承重w。如何选择物品装入背包中，使得背包恰好装满（体积），物品总重量不超过背包承重，且价值最大？
至此，该问题已经转为一个标准的二维背包问题！
关于二维背包问题的求解方法本文就不详细阐述了，网上很容易找到。
附上采用二维背包问题求解过程的部分代码
上述函数实现功能输入两个数组，返回它们均衡后，较小数组的累加和。其中部分函数的实现未全部给出（比较简单）。
至此，本题的思路已经比较明确了。但上面的代码并未完整解决题目的要求，需要稍加改进。这个就不深入讨论了。
另外，值得一提的是，实现中采用了根据数据内容来分配内存的方式，在实际使用中会存在很大的安全或性能隐患（比如，数据差距很大，会导致分配巨额内存）。
大意为：
当前数组a与数组b的各自累加和的差为
a = sum(a) - sum(b)
假设数组a的i元素与数组b的j元素互换，新的a数组与b数组各自累加和的差为
a' = sum(a) b[j] - a[i] - ( sum(b) a[i] - b[j])
= sum(a) - sum(b) - 2*(a[i] - b[j])
= a - 2* (a[i] - b[j])
假设a大于0， 那么如果能够找到这样的a[i] 与b[j], 使得 |a[i] - b[j]| 在（0，a）之间，那么交换这两个元素，数组a与数组b累加和之间的差值将变小。
据此可以得出算法
（1）计算数组a与数组b累加和差值，记为a；
（2）在数组a与b之间选择这样一组元素，它们的差值比a小；
（3）交换这组元素；
（4）重复（1），（2），（3）步，直到找不到合适的元素组即完成。
网上有类似的算法，本文就不贴代码了。
上面的算法是一个典型的贪心算法，能够得到局部最优解，但未必能够得到全局最优。http://blog.csdn.net/cwqbuptcwqbupt/article/details/7521733， 对此作了反例。
2. 重新分析：
题目的一个等价命题为，给定2n个元素，累加和为sum，从中选择n个元素，使得选择的n个元素的累加和尽量接近sum/2 。
经过这样命题转换，我们把两个数组统筹在一起了，更有全局观了（废话）。这样从一堆物品中选择出一堆且满足一定要求，首先联想到背包问题。那么能不能转换为背包问题求解呢？
考虑
我们有一个背包容量为sum/2的背包，给定物品有2n个，第i个物品的重量为w[i]，要求装入物品的个数恰好为n，且总重量尽量接近sum/2。
上面定义转换为了一个背包问题，但又与常见的01背包问题有差别。事实上，该背包有两个限制：其一是物品个数，其二是物品总重量。
那么我们为每个元素定义两个属性：其一，重量属性，其二，数量属性（或体积属性）。
那么我们的“物品”和“背包”：
有2n个物品，第i个物品体积为c[i] (均为1）, 重量为w[i]。现有一个背包， 背包体积容量为n， 承重为w。如何选择物品装入背包中，使得背包恰好装满（体积），物品总重量不超过背包承重，且总重量达到最大？
由于物品重量既是限制又是目标，稍微有点混乱，我们再引入一个物品属性：价值（不过，凑巧的是物品价值和物品质量是相等的）。再定义如下：
有2n个物品，物品i 的体积为c[i] (均为1）， 重量为 w[i], 价值为v[i] (v[i] = w[i])。现有一个背包，背包体积容量为n，承重w。如何选择物品装入背包中，使得背包恰好装满（体积），物品总重量不超过背包承重，且价值最大？
至此，该问题已经转为一个标准的二维背包问题！
关于二维背包问题的求解方法本文就不详细阐述了，网上很容易找到。
附上采用二维背包问题求解过程的部分代码
点击(此处)折叠或打开
-
int seriesbalance(int *list1, int* list2, int len)
-
{
-
int sum = 0;
-
-
int* wights;
-
int* caps;
-
int* vlues;
-
-
array_t* arraycur;
-
array_t* arraybk;
-
-
array_t* pcur;
-
array_t* pbk;
-
array_t* ptemp;
-
-
-
int pckgw;
-
int pckgc;
-
-
int col;
-
int row;
-
-
int val;
-
int i, j, k;
-
-
int drow;
-
int dcol;
-
-
wights = (int*) calloc(2 * len, sizeof(int));
-
caps = (int*) calloc(2 * len, sizeof(int));
-
vlues = (int*) calloc(2 * len, sizeof(int));
-
//to-do: do alloc success check here
-
-
-
for (i = 0; i < len; i)
-
{
-
sum = (list1[i] list2[i]);
-
-
wights[i] = list1[i];
-
wights[len i] = list2[i];
-
-
caps[i] = 1;
-
caps[len i] = 1;
-
-
vlues[i] = list1[i];
-
vlues[len i] = list2[i];
-
}
-
-
pckgw = sum / 2; // 注意这里@pckgw跟数据内容有关，非常容易引发不稳定问题
-
pckgc = len;
-
-
arraycur = newarray((pckgc1) , (pckgw1));
-
arraybk = newarray((pckgc1) , (pckgw1));
-
//do malloc success check
-
-
-
pcur = arraycur;
-
pbk = arraybk;
-
-
/*
-
__0_1_2_3_4_5_6_7_8___w_
-
0|0 0 0 0 0 0 0 0 0
-
1|x x x x x x x x x
-
2|x x x x x x x x x
-
3|x x x x x x x x x
-
-
c|
-
-
fcwv(0,0,x)
-
*/
-
for (row = 0; row <= pckgc; row)
-
{
-
for (col = 0; col <= pckgw; col)
-
{
-
if (row == 0)
-
{
-
setarray(pbk, row, col, 0);
-
}
-
else
-
{
-
setarray(pbk, row, col, (-2 * sum)); // 由于是恰好装满，那些不能满足恰好装满的选择方式都为负数
-
}
-
}
-
}
-
-
-
for (i = 0; i < 2 * len; i)
-
{
-
for(row = 1; row <= pckgc; row)
-
{
-
for(col = 1; col <= pckgw; col)
-
{
-
if (row < caps[i] || col < wights[i])
-
val = getarray(pbk, row, col ); // 不装入，当前值是上一轮对于的值
-
else
-
val = max( (getarray(pbk, row - caps[i], col - wights[i]) vlues[i]), getarray(pbk, row, col));
-
-
setarray(pcur, row, col, val);
-
}
-
}
-
-
// 交换指针
-
ptemp = pbk;
-
pbk = pcur;
-
pcur = ptemp;
-
}
-
-
-
val = -2*sum;
-
for(row = pckgc; row > 0; row--)
-
{
-
for (col = pckgw; col > 0; col--)
-
val = max(getarray(pbk, row, col), val);
-
}
-
-
free(arraycur);
-
free(arraybk);
-
free(wights);
-
free(vlues);
-
free(caps);
-
-
return val;
- }
上述函数实现功能输入两个数组，返回它们均衡后，较小数组的累加和。其中部分函数的实现未全部给出（比较简单）。
至此，本题的思路已经比较明确了。但上面的代码并未完整解决题目的要求，需要稍加改进。这个就不深入讨论了。
另外，值得一提的是，实现中采用了根据数据内容来分配内存的方式，在实际使用中会存在很大的安全或性能隐患（比如，数据差距很大，会导致分配巨额内存）。
给主人留下些什么吧！~~