问题描述
你有一架天平和 N 个砝码，这N 个砝码重量依次是 1,2,⋅⋅⋅,W1,W2,⋅⋅⋅,WN。
请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数 N。
第二行包含 N 个整数：1,2,3,⋅⋅⋅,W1,W2,W3,⋅⋅⋅,WN。
输出格式
输出一个整数代表答案。
样例输入
3
1 4 6样例输出
10样例说明
能称出的 1010 种重量是：1、2、3、4、5、6、7、9、10、111、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。
拿到这个题，主要思路是：
// 分为三种情况
1.dpi-1如果上一次的砝码是1说明可以称出这个重量，我们直接复制下来就行了
2.dpi-1)]表示上一次称砝码放天平左边能不能配出这个重量
3.dpi-1]表示上一次称砝码放天平右边能不能配出这个重量
以上三种情况满足一种就说明此重量可以配出
public class 砝码称重 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int count = 0;// 统计能配出的个数
int[] w = new int[101];
boolean[][] dp = new boolean[101][100001];
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long sum = 0L;
for (int i = 1; i <= n; i++) {
w[i] = sc.nextInt();// 每个砝码的重量
sum += w[i];// 砝码最大重量
}
for (int i = 1; i <= n; i++) {// 有多少个砝码
for (int j = 1; j <= sum; j++) {// 砝码最大重量
if (j == w[i]) {// 能称出砝码的质量就直接赋值为1说明可以称
dp[i][j] = true;
} else {
// 分为三种情况1.dp[i-1][j]如果上一次的砝码是1说明可以称出这个重量，我们直接复制下来就行了
// 2.dp[i-1][abs(j-w[i])]表示上一次称砝码放天平左边能不能配出这个重量
// 3.dp[i-1][j+w[i]]表示上一次称砝码放天平右边能不能配出这个重量
// 以上三种情况满足一种就说明此重量可以配出
dp[i][j] = dp[i - 1][j] || dp[i - 1][Math.abs(j - w[i])] || dp[i - 1][j + w[i]];
}
}
}
for (int i = 1; i <= sum; i++) {
// System.out.print(dp[n][i] + " ");
if (dp[n][i]) {
count++;
}
}
System.out.println(count);
sc.close();
}}