蓝桥杯——砝码称重（JAVA）

题目：

你有一架天平和 N个砝码，这 N 个砝码重量依次是 W_1, W_2, · · · , W_N​。

请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。

输入格式

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

第二行包含 N 个整数：W_1, W_2, W_3, · · · , W_N​。

输出格式

输出一个整数代表答案。

样例输入

3
1 4 6

样例输出

10

样例说明

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

1 = 1；

2 = 6 − 4 (2=6−4(天平一边放 66，另一边放 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。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

代码： 

import java.util.Scanner;
public class main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N= sc.nextInt();
        int fama[]=new int[N];     //储存各砝码重量
        int sum=0;                 //储存所有砝码可称出的最大重量
        int max=0;                 //储存最多可以称出几种重量
        for (int i=0;i<N;i++){
            fama[i]=sc.nextInt();
            sum+=fama[i];
        }
        int dp[][]=new int[N+1][2*sum];  //二维数组dp[i][j]  i表示前i个砝码j表示前i个砝码是否可以称出j的重量  设置成2*sum防止数组越界
        dp[0][0]=1;               //0个砝码一定可以称出0的重量所以直接设为1
        for (int i=1;i<=N;i++){
            for (int j=sum;j>=0;j--){
                if (dp[i-1][j]==1||dp[i-1][Math.abs(j-fama[i-1])]==1||dp[i-1][j+fama[i-1]]==1){
                    dp[i][j]=1;
                }
                else {
                    dp[i][j]=0;
                }
            }
        }                    //先从第一个砝码开始在零个砝码的基础上放到天平左边减去此砝码重量放到右边加上此砝码重量，依次类推获得可以称出的所有重量。
        for(int  j= 1; j<= sum; j++)
            if(dp[N][j]==1) max++;
        System.out.println(max);  //dp[N][j]==1时表示N个砝码可以称出j的重量由于重量0不算入最终结果所以j从1开始，则max加一最终输出max
        sc.close();
    }
}

思路：运用dp(动态规划)思想，dp[i][j]表示i个砝码是否可以称出j的重量。

由于0个砝码一定可以称出0这个重量所以dp[0][0]==1，之后在此基础上加入第一个砝码，放到天平左边则减去第一个砝码重量，放到右边则加上第一个砝码的重量依次类推得到N个砝码所能称出的所有重量（最终答案重量0排除在外所以从重量1开始遍历并进行统计）。