Codility - Delta 2011 - min_abs_sum

题目见 https://codility.com/demo/take-sample-test/delta2011/

这是一道很有意思的题目。有N个数的数组A，令有N个数的数组S，S中元素取值为1或-1，则定义 val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }| ，现在要求 val(A, S) 的最小值。很显然，本质是将数组A分成两部分，使得两部分的差最小。不幸的是，数组均分问题是很困难的，其实是NPC的，而题目要求时间复杂度为 O(N*max(abs(A))²) ，并且空间复杂度为 O(N+sum(abs(A))) ，似乎不可能实现…… 但是呢，题目给定了A中元素的取值范围是 [-100, 100] 中的整数，利用这个性质，就能极大地降低复杂度。

首先对数组做处理，负数转换成对应正数，零去掉，计数排序统计有多少个不同元素及其对应个数，并累加所有数的和sum，不妨记b=sum/2，不同元素个数为m，则目标转换为在m个不同元素中挑出若干个元素（每个元素可以重复多次，但少于它们的出现次数），使得它们的和不大于b并尽量接近。到了这里，应该有点熟悉的感觉了吧。对了，其实这就是0-1背包问题！

记 f[i][j] 为只允许选前 i 个元素，总和不超过 j ，则有 f[i][j] = max { f[i-1][j], f[i][j-D[i]]+D[i] }, 其中 D[i] 为第 i 个元素对应的值。由于每种元素的数量不是无穷多，因此对每个 f[i][j] ，都需要记录第 i 种元素的消耗数量，保证小于该元素的出现次数。

代码见 https://github.com/phiphy/codility/blob/master/min_abs_sum.c

Keywords: 0-1 knapsack