【资源限制】
内存限制：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个砝码是否能称出重量j
boolean[][] 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]的值也必须为0
arr[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);
}
}
文章出处登录后可见！
