题解 | #称砝码#动态规划

称砝码

https://www.nowcoder.com/practice/f9a4c19050fc477e9e27eb75f3bfd49c

题目分析:

可以直接看成:给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);

全部评论

相关推荐

粗心的雪碧不放弃:纯学历问题,我这几个月也是一直优化自己的简历,后来发现优化到我自己都觉得牛逼的时候,发现面试数量也没有提升,真就纯学历问题
点赞 评论 收藏
分享
像好涩一样好学:这公司我也拿过 基本明确周六加班 工资还凑活 另外下次镜头往上点儿
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务