砝码称重（JAVA）

题目：

你有一架天平和 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 (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();
    }
}