【资源限制】

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

【问题描述】

        你有一架天平和N个砝码，这N个砝码重量依次是W1，W2，.… . , Wn 。请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

【输入格式】

        输入的第一行包含一个整数N。

        第二行包含N个整数:W1,W2,W3，… ，Wn 。

【输出格式】

        输出一个整数代表答案。

【样例输入】

        3

        1        4        6

【样例输出】

        10

【样例说明】

        能称出的10种重量是:1、2、3、4、5、6、7、9、10、11。

        1 = 1；

        2=6-4(天平一边放6，另一边放4)；

        3=4- 1；

        4=4；

        5=6-1；

        6=6；

        7=1＋6；

        9=4＋6-1；

        10=4＋6；

        11=1＋4＋6

【评测用例规模与约定】

        对于50%的评测用例，1≤N≤15。

        对于所有评测用例，1≤N ≤ 100，N个砝码总重不超过100000。

【思路与分析】

        该题初看没什么头绪，但仔细读题并结合数据结构的相关知识便可以发现制胜之道。利用该题所给的题例，我自然而然的联想到了——动态规划法。

        而动态规划法解题的关键是什么？对，状态转移方程。只需要根据所给题例解析出背后的“规律”，也就是方程即可。

        理清思路，开始解题。
        首先，我们要明确砝码有几种状态【w：重量首字母】

                1、放在左边：arr[i][j] = arr[i-1][j-w[i]] （前i-1个砝码是否能称出j-当前砝码重量   j）

                2、放在右边：arr[i][j] = arr[i-1][j+w[i]]（前i-1个砝码是否能称出j+当前砝码重量  j）

                3、不进行放置：arr[i][j] = arr[i-1][j]    （前i-1个砝码是否能称出重量  j）

        由上述式子可得状态转移方程如下：

                arr[i][j] = arr[i-1][j-w[i]] || arr[i][j] = arr[i-1][j+w[i]]  || arr[i][j] = arr[i-1][j]

        不难发现，该式子要想使得 arr[i-1][j-w[i]] 为 true，首先要让arr[0][0] 及 arr[i][0] 为 true，这样在 j-w[i]=0 时，arr[i-1][j-w[i]] 才能为 true。

【代码】

import java.util.Scanner;public class Main {public static void main(String[] args) {//arr[i][j]表示前i个砝码是否能称出重量jboolean[][] arr = new boolean[102][100003];    //100003 3代表3种状态Scanner sc = new Scanner(System.in);int num = sc.nextInt();int[] w = new int[102];     //该数组用于存放各个砝码的重量int sum = 0;                //砝码数量和for (int i=1;i<=num;i++){w[i] = sc.nextInt();sum += w[i];}arr[0][0] = true;      //arr[0][0]的值为true，意为帮助arr[i][j]计算for (int i=1;i<=n;i++){for (int j=0;j<=sum;j++){   //arr[i][0]的值也必须为0arr[i][j] = arr[i-1][j]||arr[i-1][Math.abs(j-w[i])]||arr[i-1][Math.abs(j+w[i])];}}int res = 0;    //存储结果数for (int j=1;j<=sum;j++){   if (arr[num][j])    //能测到这个重量res++;    //结果++}System.out.println(res);}
}