[Java知识库]砝码称重（Java）

砝码称重

分析

将砝码独立来看，
在当前砝码称出重量x的情况下，对于砝码i都有三种操作：

1. x+砝码i的重量（放同侧）
2. x-砝码i的重量（放异侧）
3. x（不放）

显然前面两种操作才有可能产生不同的重量。
另外砝码i一定能称出其自身的重量

又考虑到set能够用于排除相等的元素
由于砝码称出的重量是正的，因此将操作获得的结果取绝对值再放入集合中
因此有如下代码：

import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;

public class Main{
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//ans用于存放称出的不同重量
		Set<Integer> ans = new HashSet<Integer>();
		
		int n = sc.nextInt();
		
		for(int i = 0; i < n; i++) {
			int t = sc.nextInt();
			//由于set在遍历的过程中不能添加元素，因此用另外一个set来存放该砝码称出的重量
			Set<Integer> temp = new HashSet<Integer>();
			Iterator<Integer> it = ans.iterator();
			while(it.hasNext()) {
				int m = it.next();
				temp.add(m+t);
				temp.add(Math.abs(m-t));
			}
			//再全部加入到ans集合中
			ans.addAll(temp);
			//砝码必定可以称出自身重量
			ans.add(t);
		}
		//要注意的是！！重量0并不能称出来！！因此要去掉元素0
		//我栽在这里了（佛）
		ans.remove(0);
		//最后只需要输出答案集中的个数即可
		System.out.println(ans.size());
	}

}

另外，我还看到有用dp做的，思路其实差不多
附上代码：

import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		//存放砝码重量
		int a[] = new int[n];
		int sum = 0;
		for(int i = 0; i < n; i++){
			a[i] = sc.nextInt();
			sum += a[i];
		}
		
		int cnt = 0;
		boolean dp[][] = new boolean[n][sum+1];
	
		dp[0][a[0]] = true;
		
		for(int i = 1; i < n; i++){
			//将上一个状态复制过来
			for(int j = 1; j <= sum; j++)
				dp[i][j] = dp[i-1][j];
			dp[i][a[i]] = true;
			
			for(int j = 1; j <= sum; j++){
				dp[i][j+a[i]] = true;
				dp[i][Math.abs(j-a[i])] = true;
			}
			
	}
}