蓝桥杯之“砝码称重“解题思路,含图解(Java)

这篇具有很好参考价值的文章主要介绍了蓝桥杯之“砝码称重“解题思路,含图解(Java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

问题描述

你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W_1, W_2, · · · , W_N。

请你计算一共可以称出多少种不同的重量? 注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 N。

第二行包含 N 个整数:W_1, W_2, W_3, · · · , W_N​。

输出格式

输出一个整数代表答案。

样例输入

3
1 4 6

样例输出

10

样例说明

能称出的 10 种重量是:1、2、3、4、5、6、7、9、10、11

问题分析:

首先分析问题的类型,每一个砝码只能选择取或者不取,类似于01背包问题。

每一种不同重量都可以从计算上次秤出的重量中上得出,这句话可能大家没有太明白。

我这里解释一下,比如说:

假设砝码a,b,c的重量分别为1,4,6

一开始,天平上只有砝码a,天平上只有砝码a说明秤出的重量只有1。

此时我们可以不放砝码b,或者放砝码b

放入砝码b就会秤出重量5和3,即4+1=5和4-1=3,我们可以把5和3作为新的砝码,等放入下一个砝码时,就可以在原来秤出的重量上计算新的重量

不放入b,天平上还是原来的重量

算法图解:

图解一:分析先放入a,再放入b,在放入c的图解

蓝桥杯之“砝码称重“解题思路,含图解(Java)

图解二:分析不放入a,再放入b,再放入c的情况

蓝桥杯之“砝码称重“解题思路,含图解(Java)

以上的图解只分析了两种情况 ,所有需要画出所有的情况,就会画出一颗树。

左子树代表选择放入新的砝码,右子树表示不放入新的砝码,也就是继承上次的重量。

注意:左子树可能会秤出两种重量

蓝桥杯之“砝码称重“解题思路,含图解(Java)

根据以上图解我们可以得出,每次放入新的砝码,都可以从上一次秤得的重量中计算得出。

完整代码如下:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        Set<Integer> set = new HashSet<>();
        int n = scan.nextInt();
        int[] fama = new int[n];
        for (int i = 0; i < n; i++) {
            fama[i] = scan.nextInt();
        }
        //初始化set,表示一开始天平上没有砝码,重量为0
        set.add(0);
        for (int i = 0; i < n; i++) {
            //在没放入新的砝码前,将秤得的所有重量放入list集合中
            List<Integer> list = new ArrayList<>(set);
            for (int k : list) {
                //相加和相减取绝对值产生新的两个重量,并加重量放入set集合中
                //注意:如果新秤得的重量在原来的set集合存在,将不被放入set中
                set.add(k + fama[i]);
                set.add(Math.abs(k - fama[i]));
            }
        }
        //移除0元素
        set.remove((Object)0);
        //输出set集合大小,即秤得的重量数
        System.out.println(set.size());
    }
}

运行结果:

蓝桥杯之“砝码称重“解题思路,含图解(Java)

 当然了,本人也使用过递归爆搜的解法,由于利用暴力搜索的方法会产生大量的重复计算,

所以提交答案会提示超时,代码给有需要的读者作为参考:

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        Main main = new Main();
        Set<Integer> result = new HashSet<>();
        int n = scan.nextInt();
        int[] fama = new int[n];
        for(int i = 0; i < n; i++){
            fama[i] =  scan.nextInt();
        }
        main.rese(0,fama,0,0,n,result);
        System.out.println(result.size());
        scan.close();
    }

    public void rese(int a,int[] fama,int sum1, int sum2,int n,Set<Integer> result){
        if(sum1 - sum2 > 0){
            result.add(sum1 - sum2);
        }
        for(int i = a; i < n; i++){
            sum1 += fama[i];
            rese(i+1,fama,sum1,sum2,n,result);
            sum1 -= fama[i];
            sum2 += fama[i];
            rese(i+1,fama,sum1,sum2,n,result);
            sum2 -= fama[i];
        }
    }
}

 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家

跳转到教程

finally,如果读者们可以理解我这个解法当然我是最开心的,虽然在表述上没这么清晰吧,但是图解是我的全部想法,这个解法也是我自己独立想出来的,感谢您的阅读!🏃文章来源地址https://www.toymoban.com/news/detail-405453.html

到了这里,关于蓝桥杯之“砝码称重“解题思路,含图解(Java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第十四届蓝桥杯大赛软件赛省赛-试题 B---01 串的熵 解题思路+完整代码

    欢迎访问个人网站来查看此文章:http://www.ghost-him.com/posts/db23c395/ 对于一个长度为 n 的 01 串 S = x 1 x 2 x 3 . . . x n S = x_{1} x_{2} x_{3} ... x_{n} S = x 1 ​ x 2 ​ x 3 ​ ... x n ​ ,香农信息熵的定义为 H ( S ) = − ∑ 1 n p ( x i ) l o g 2 ( p ( x i ) ) H(S ) = − {textstyle sum_{1}^{n}} p(x_{i})log_{2} (p

    2023年04月10日
    浏览(43)
  • 蓝桥杯之我见

    关于蓝桥杯,应该有很多人不知道这是一个什么样的比赛。但是作为一名合格的程序员,就算之前没有参加过蓝桥杯的比赛,或者没听说过蓝桥杯,读完本篇文章再说不知道蓝桥杯,就有点不合适了吧?!那么本文就来简单聊一下关于蓝桥杯相关的内容,“扫盲科普”一下。

    2023年04月14日
    浏览(41)
  • 蓝桥杯之贪心

    将股票价格的变动抽象成折线图,将每个上升阶段累加起来(每次的累加并不一定代表真实的一次买卖交易,比如两段连续上升的折线,只进行了一次买卖,但对两段上升折线分别累加的收益结果是一致的) 我们设在仓库左边的所有点,到仓库的距离之和为p,右边的距离之和

    2023年04月09日
    浏览(35)
  • 蓝桥杯之算法模板题 Python版

    记录一下算法模板题,这样方便查阅和学习,希望好好加油 dp, LIS ** 01背包 动态转移方程 f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v ] + w ) ( j v ) f[i][j] = max(f[i-1][j], f[i-1][j-v] + w)(jv) f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v ] + w ) ( j v ) 完全背包 一般就是

    2023年04月08日
    浏览(45)
  • 蓝桥杯之找素数(填空题+编程题)

     强烈推荐先看一下这篇蓝桥杯之素数及相关判断方法(看这一篇就够了)_冷兮雪的博客-CSDN博客 目录 一、找素数(填空题)  1、题目  2、题目解读  3、代码  二、找素数(编程题) 1、题目 2、题目解读   3、代码 找素数 - 蓝桥云课 (lanqiao.cn)  1、题目 题目描述 本题为填

    2023年04月18日
    浏览(85)
  • 蓝桥杯之素数及相关判断方法(看这一篇就够了)

    目录 一、素数及相关概念  1、素数的性质  2、有关素数的猜想  二、素数的判断方法  1、根据性质去判断  2、改进1方法(缩小比较范围√n) 3、再次分析素数的特点,得出规律 问题:枚举n以内所有素数  4、埃氏筛法(埃拉托斯特尼筛法) 5、欧拉筛法(埃氏筛法的优化

    2023年04月15日
    浏览(70)
  • Frida主动调用java函数来爆破解题思路

    利用Frida去调用java代码中的类,然后爆破。算是一种主动调用的方法。主动调用可以用于爆破,模拟程序部分执行,需要注意的知识点是在java代码中的static类型数据在爆破过程中需要每次都对这种类型值重新设置。因为static类型在所有实例中都是统一,修改一个实例就会修改

    2024年02月13日
    浏览(71)
  • 华为OD机试真题B卷 Java 实现【字符统计】,附详细解题思路

    华为OD机试 2023B卷题库疯狂收录中,刷题 点这里 输入一个只包含小写英文字母和数字的字符串,按照不同字符统计个数由多到少输出统计结果,如果统计的个数相同,则按照ASCII码由小到大排序输出。 数据范围:字符串长度满足 1≤len(str)≤1000 。 一个只包含小写英文字母和

    2024年02月07日
    浏览(49)
  • 华为OD机试真题B卷 Java 实现【查字典】,附详细解题思路

    华为OD机试 2023B卷题库疯狂收录中,刷题 点这里 输入一个单词前缀和一个字典,输出包含该前缀的单词。 单词前缀+字典长度+字典。 字典是一个有序

    2024年02月07日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包