第十二届蓝桥杯真题Java B组 【砝码称重】

思路：
采用动态规划（DP），找到状态转移方程就很好解了。对于每个砝码的放置有3种状态：
不放：isOk[i][j] = isOk[i-1][j] （结果为前i-1个是否能称出重量j）
放一边：isOk[i][j] = isOk[i-1][j-w[i]] （结果为前i-1个是否能称出j减去当前砝码重量j）
放另一边：isOk[i][j] = isOk[i-1][j+w[i]] （结果为前i-1个是否能称出j+当前砝码重量j）
这样可以得到状态转移方程：
isOk[i][j] = isOk[i-1][j] || isOk[i-1][j-w[i]] || isOk[i-1][j+w[i]]
要使isOk[0][0]和isOk[i][0]为true，这样之后j-w[i]=0时，才能使isOk[i-1][j-w[i]]为真。
完整代码：

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        boolean[][] isOk = new boolean[102][100003];    //  isOk[i][j]表示前i个砝码是否能称出j重量
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] w = new int[102];     //  各个砝码的重量
        int sum = 0;                //  砝码的和
        for (int i=1;i<=n;i++){
            w[i] = sc.nextInt();
            sum += w[i];
        }
        isOk[0][0] = true;      //  要使0,0的值为true，辅助isOk[i][j]的计算
        for (int i=1;i<=n;i++){
            for (int j=0;j<=sum;j++){   //  isOk[i][0]d的值也必须为0，道理同上
                isOk[i][j] = isOk[i-1][j]||isOk[i-1][Math.abs(j-w[i])]||isOk[i-1][Math.abs(j+w[i])];
            }
        }
        int res = 0;
        for (int j=1;j<=sum;j++){   //  计算有多少种重量
            if (isOk[n][j])
                res++;
        }
        System.out.println(res);
    }
}