用dp做 思路注释写的很清晰 有需要的可以看一下

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

public class Main {

    static int N;

    static int[] W;

    static int COUNT;

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner scanner = new Scanner(System.in);

        N = scanner.nextInt();

        W = new int[N];

        int sum = 0;

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

            sum += W[i] = scanner.nextInt();

        }

        COUNT = sum;

        //Arrays.sort(W);

        dp();

}

public static void dp() {

boolean[][] dp = new boolean[W.length][COUNT + 1];

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

//对于dp数组的初始化  对于目标为0的配重 都置为true 对于每一行和砝码重量相同的目标配重也置为true

dp[i][0] = true;

dp[i][W[i]] = true;

}

//从第二块砝码开始递推

for (int i = 1; i < dp.length; i++) {

//第一列配重为0跳过

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

//如果在加入这块砝码前就已经能够组成配重 那么不需要放当前砝码 直接置1即可

if (dp[i - 1][j]) {

dp[i][j] = true;

}

//当前砝码和目标物放到同一边 如果不超重并且前面没有当前砝码时已经可以凑出目标物和当前砝码重量总和相同的数量

//那么就可以置为1

if (W[i] + j <= COUNT && dp[i - 1][W[i] + j]) {

dp[i][j] = true;

}

//当前砝码放在目标物的另一边 这种情况 当前砝码可能比目标物重或轻 他们的差值就考虑找到之前的砝码来补足两边的重量

if (dp[i - 1][Math.abs(j - W[i])]) {

dp[i][j] = true;

}

}

}

int sum = 0;

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

if (dp[N - 1][i]) {

sum++;

}

}

System.out.println(sum);

}

}