public static int maxPresent (int[] presentVec) {

int n = presentVec.length;

if (n == 0) {

return 0;

}

int sum = 0;

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

sum += presentVec[i];

}

//简化为背包问题

int v = (sum + 1) / 2;

int[] dp = new int[v + 1];

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

int p = presentVec[i];

for (int j = v; j >= p; j--) {

dp[j] = Math.max(dp[j], dp[j - p] + p);

}

}

return Math.abs(sum - 2 * dp[v]);

}

public static void main(String[] args) {

int[] nums = new int[]{41,467,334,1,169,224,478,358};

System.out.println(maxPresent2(nums));

}

public static int maxPresent2 (int[] presentVec) {

int n = presentVec.length;

if (n == 0) {

return 0;

}

int sum = 0;

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

sum += presentVec[i];

}

//简化为背包问题

int v = (sum + 1) / 2;

int[][] dp = new int[n + 1][v + 1];

for (int i = 1; i <= n; i++) {

int p = presentVec[i - 1];

for (int j = 1; j <= v; j++) {

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

if (j >= p) {

dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - p] + p);

}

}

}

return Math.abs(sum - 2 * dp[n][v]);

}