[codility]Min-abs-sum

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

0-1背包问题的应用。我自己一开始没想出来。“首先对数组做处理，负数转换成对应正数，零去掉，计数排序统计有多少个不同元素及其对应个数，并累加所有数的和sum，不妨记b=sum/2，不同元素个数为m，则目标转换为在m个不同元素中挑出若干个元素（每个元素可以重复多次，但少于它们的出现次数），使得它们的和不大于b并尽量接近。到了这里，应该有点熟悉的感觉了吧。对了，其实这就是0-1背包问题！” 参考http://phiphy618.blogspot.jp/2013/05/codility-delta-2011-minabssum.html

第一次的代码并未完全通过，75分，大数据全挂。原因是这里一个元素可以出现多次，是多重背包问题。

// you can also use imports, for example:

// import java.math.*;

class Solution {

    public int solution(int[] A) {

        // write your code here...

    	if (A.length == 0) return 0;

    	int sum = 0;

    	int max = 0;

    	for (int i = 0; i < A.length; i++) {

    		if (A[i] < 0) A[i] = -A[i];

    		sum += A[i];

    	}

    	int target = sum / 2;

    	int dp[][] = new int[A.length][target];

    	for (int i = 0; i < A.length; i++) {

    		for (int j = 0; j < target; j++) {

    			// j+1 is the weight limit

    			if (i == 0)

    			{

    				if (A[i] <= (j+1)) {

    					dp[i][j] = A[i];

    				}

    				else

    				{

    					dp[i][j] = 0;

    				}

    			}

    			else // i != 0

    			{

    				int w1 = dp[i-1][j];

    				int w2 = 0;

    				if (j-A[i] >=0 ) {

    					w2 = dp[i][j-A[i]] + A[i];

    				}

    				dp[i][j] = w1 > w2 ? w1 : w2;

    			}

    		}

    	}

    	max = dp[A.length - 1][target - 1];

    	return (sum - max * 2);

    }

}

第二次参考了cp博士的文章，处理了多重背包的优化，并用了滚动数组：http://blog.csdn.net/caopengcs/article/details/10028269

// you can also use includes, for example:

// #include <algorithm>

int solution(const vector<int> &A) {

    // write your code in C++98

    int len = A.size();

    int sum = 0;

    int M = 0;

    for (int i = 0; i < len; i++) {

        int x = 0;

        x = A[i] > 0 ? A[i] : -A[i];

        sum += x;

        if (x > M)

            M = x;

    }

    vector<int> count;

    count.resize(M+1);

    for (int i = 0; i < len; i++) {

        int x = 0;

        x = A[i] > 0 ? A[i] : - A[i];

        count[x]++;

    }

    int target = sum / 2;

    int largest = 0;

    vector<int> dp(target+1, -1);

    for (int i = 0; i <= M; i++) {

        if (count[i] > 0) {

            for (int j = 0; j <= target; j++) {

                if (j == 0) dp[j] = count[i];

                if (dp[j] >= 0) {

                    dp[j] = count[i];

                    if (j > largest)

                        largest = j;

                }

                else if (j - i >= 0 && dp[j - i] > 0) {

                    dp[j] = dp[j - i] - 1;

                    if (j > largest)

                        largest = j;

                }

                else {

                    dp[j] = -1;

                }

            }

        }

    }

    return abs(sum - 2 * largest);

}

巴特西

[codility]Min-abs-sum

最新文章

热门文章