Chinaunix首页 | 论坛 | 博客
  • 博客访问: 671464
  • 博文数量: 141
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1114
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

小公司研发总监,即当司令也当兵!

文章分类

全部博文(141)

分类: LINUX

2016-11-20 21:35:20

题目


有两个序列a,b,大小都为n,序列元素的值任意整数,无序;
要求:通过交换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。如何选择物品装入背包中,使得背包恰好装满(体积),物品总重量不超过背包承重,且价值最大?

至此,该问题已经转为一个标准的二维背包问题!

关于二维背包问题的求解方法本文就不详细阐述了,网上很容易找到。
附上采用二维背包问题求解过程的部分代码


点击(此处)折叠或打开

  1. int seriesBalance(int *list1, int* list2, int len)
  2. {
  3.     int sum = 0;
  4.     
  5.     int* wights;
  6.     int* caps;
  7.     int* vlues;
  8.     
  9.     array_t* arrayCur;
  10.     array_t* arrayBk;

  11.     array_t* pCur;
  12.     array_t* pBk;
  13.     array_t* pTemp;
  14.     

  15.     int pckgW;
  16.     int pckgC;
  17.     
  18.     int col;
  19.     int row;
  20.     
  21.     int val;
  22.     int i, j, k;
  23.     
  24.     int drow;
  25.     int dcol;

  26.     wights = (int*) calloc(2 * len, sizeof(int));
  27.     caps = (int*) calloc(2 * len, sizeof(int));
  28.     vlues = (int*) calloc(2 * len, sizeof(int));
  29.     //TO-DO: do alloc success check here
  30.     
  31.     
  32.     for (i = 0; i < len; i++)
  33.     {
  34.         sum += (list1[i] + list2[i]);
  35.         
  36.         wights[i] = list1[i];
  37.         wights[len + i] = list2[i];
  38.         
  39.         caps[i] = 1;
  40.         caps[len + i] = 1;
  41.         
  42.         vlues[i] = list1[i];
  43.         vlues[len + i] = list2[i];
  44.     }
  45.     
  46.     pckgW = sum / 2; // 注意这里@pckgW跟数据内容有关,非常容易引发不稳定问题
  47.     pckgC = len;

  48.     arrayCur = newArray((pckgC+1) , (pckgW+1));
  49.     arrayBk = newArray((pckgC+1) , (pckgW+1));
  50.     //do malloc success check
  51.     

  52.     pCur = arrayCur;
  53.     pBk = arrayBk;

  54.     /*
  55.     __0_1_2_3_4_5_6_7_8___w_
  56.     0|0 0 0 0 0 0 0 0 0
  57.     1|X X X X X X X X X
  58.     2|X X X X X X X X X
  59.     3|X X X X X X X X X
  60.     
  61.     c|
  62.     
  63.     fcwv(0,0,x)
  64.     */
  65.     for (row = 0; row <= pckgC; row++)
  66.     {
  67.         for (col = 0; col <= pckgW; col++)
  68.         {
  69.             if (row == 0)
  70.             {
  71.                 setArray(pBk, row, col, 0);
  72.             }
  73.             else
  74.             {
  75.                 setArray(pBk, row, col, (-2 * sum)); // 由于是恰好装满,那些不能满足恰好装满的选择方式都为负数
  76.             }
  77.         }
  78.     }

  79.     
  80.     for (i = 0; i < 2 * len; i++)
  81.     {
  82.         for(row = 1; row <= pckgC; row++)
  83.         {
  84.             for(col = 1; col <= pckgW; col++)
  85.             {
  86.                 if (row < caps[i] || col < wights[i])
  87.                     val = getArray(pBk, row, col ); // 不装入,当前值是上一轮对于的值
  88.                 else
  89.                     val = MAX( (getArray(pBk, row - caps[i], col - wights[i]) + vlues[i]), getArray(pBk, row, col));
  90.                 
  91.                 setArray(pCur, row, col, val);
  92.             }
  93.         }

  94.         // 交换指针
  95.         pTemp = pBk;
  96.         pBk = pCur;
  97.         pCur = pTemp;
  98.     }
  99.     
  100.     
  101.     val = -2*sum;
  102.     for(row = pckgC; row > 0; row--)
  103.     {
  104.         for (col = pckgW; col > 0; col--)
  105.             val = MAX(getArray(pBk, row, col), val);
  106.     }
  107.     
  108.     free(arrayCur);
  109.     free(arrayBk);
  110.     free(wights);
  111.     free(vlues);
  112.     free(caps);
  113.     
  114.     return val;
  115. }

上述函数实现功能输入两个数组,返回它们均衡后,较小数组的累加和。其中部分函数的实现未全部给出(比较简单)。

至此,本题的思路已经比较明确了。但上面的代码并未完整解决题目的要求,需要稍加改进。这个就不深入讨论了。
另外,值得一提的是,实现中采用了根据数据内容来分配内存的方式,在实际使用中会存在很大的安全或性能隐患(比如,数据差距很大,会导致分配巨额内存)。
阅读(2858) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~