题目分析:
可以直接看成:给n个砝码,求能称出的不同的重量数。
暂不考虑质量相同的砝码怎么办,一视同仁
方法一:Set直接去重
假设有3个砝码,质量分别为:1、1、2。
1个砝码都没可以称出的结果:0。
加第1个砝码可以称出的结果:0 、1。
加第2个砝码可以称出的结果:0 、1、2。
加第2个砝码可以称出的结果:0 、1、2、3、4。
规律就是,当我每次加一个砝码,就有两种情况。
情况一:我不用这个砝码,那可以称出的结果就是上一次的结果,保持不变。
情况二:我用这个砝码,那就是上一次可以称出的结果加上这个砝码质量
把情况一和情况二加起来,去重(用set),就是当前能称出的质量
//关键代码类似如下
//1、遍历每一个砝码,当前砝码的质量为m。类似于我循环地去外面拿一个砝码,质量为m.
for (Integer m : fama) {
//2、拿到砝码后,需要对没拿砝码前的所有可以称出的结果进行遍历,
for (Integer temp : result_set) {
//3、没拿砝码前的所有可以称出的结果加上当前拿的砝码
result.add(temp + m );
//4、集合本身里面就已经有上一次的结果,所以直接把情况二的结果放进去就可以
}
}
方法二:动态规划
给一堆砝码,能称出的最小质量为0,最大质量是所有砝码的总和, 假设最大值为max。所以可以定义
dp = new boolean[max +1]
然后从0到max,遍历dp数组,如果质量n可以称的出,那么dp[n]=true,否则是false。统计dp数组中true的个数就是结果。
关键点:怎么判断一个质量能不能被称的出呢?
假设需要称一个质量n,其中有一个砝码质量为m1,如果n能被这堆砝码称出来,那么n-m1这个质量肯定也可以称出来。
所以要称n ,那就先称n-m1,然后称n-m1时,同理它又得先称n-m1-m2。一直到0。
boolean[] dp = new boolean[max+1];
dp[0] = true;
int count = 1;
for (Integer m : fama) { //循环每一个砝码
for (int i = max; i >= m; i--) {
if (dp[i-m] && !dp[i]){
dp[i] = true;
count++;
}
}
}
System.out.println(count);

京公网安备 11010502036488号