Chaim

用户名：YuQingming

访问量：3446

签　名：

欲善其事必先利器

等　　级
排　　名	510
经　　验	4400
参赛次数	3
文章发表	8
年　　龄	19
在职情况	学生
学　　校	HBNU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

【滑动窗口】数组求和-题解（Java代码）
浏览：565

你可能喜欢

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【详细】蓝桥杯算法提高VIP-盾神与砝码称重-题解（Java代码）

　　作者: Chaim　　　　发表时间：2020-06-04 00:05:21 浏览：685　|　评论：2　

原题链接：蓝桥杯算法提高VIP-盾神与砝码称重

有一个关键的坑：砝码可以加载天平的左边、右边，也可以不加

细节注意：只要求输出m行，所以程序运行结果的尾部不能出现多余的空行

分析

题目要是一个一个砝码用循环判断去处置，那么不是做不出来，就是时间超了

显然，可以用递归处理

分三步走：
递归参数：

现在所加砝码的重量(抵消放在物品一端的砝码重量)，砝码数组、物品重量、现在已经放置的砝码个数
![](http://yuhang.site/wp-content/uploads/2020/06/120.png)

递归出口：

当现在加的砝码，和物体的重量相等的时候，可以称出重量，递归结束；如果当现在加的砝码个数已经达到上限了（没有砝码可以用了），称不出来，单次子递归调用结束
![](http://yuhang.site/wp-content/uploads/2020/06/121.png)
递归规律：

每一层调用递归的时候，都比上一层多使用了一个砝码，而这个砝码可以选择不加，直接扔掉，或者可以加在物品一端，或者加在物品的另外一端
![](http://yuhang.site/wp-content/uploads/2020/06/122.png)

所有代码：
```java

import java.util.Scanner;

public class Main {
    /** 标记是否能称出来 */
    static boolean aBoolean;

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        int weight;
        for (int i = 0; i < m; i++) {
            weight = scanner.nextInt();
            aBoolean = false;
            judge(0,arr,weight,0);
            if(aBoolean){
                // 防止尾部多输出一行空格
                if(i!=m-1){
                    System.out.println("YES");
                    continue;
                }
                System.out.print("YES");
            }else {
                if(i!=m-1){
                    System.out.println("NO");
                    continue;
                }
                System.out.println("NO");
            }
        }

}

/** 判断是否能称出来，
     * w:当前所加砝码的重量
     * arr[]:砝码重量数组
     * weight:当前物体的重量
     * n：当前所放砝码的个数*/
    private static void judge(int w,int[] arr, int weight,int n) {
        // 如果重量达到了，就可以称出来
        if(w == weight){
            aBoolean = true;
            return;
        }
        // 如果所有的砝码用完了还不能称出来
        if(n == arr.length){
            return;
        }
        // 当前砝码放在物体另一边
        judge(w + arr[n],arr,weight,n+1);
        // 不放当前砝码
        judge(w,arr,weight,n+1);
        // 当前砝码放在物体这一边
        judge(w - arr[n],arr,weight,n+1);
    }

}
```

个人学习网址：http://yuhang.site/

0.0分

5 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

isLIUJIAO呐

大佬牛牛牛！

2021-11-26 16:38:22

长孙小野

23-26行、29-32行不写也是正确的

2021-01-18 16:24:17

Chaim

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

【偶数求和】（C++代码）

九宫重排（C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

人见人爱A+B （C语言代码）

【详细】蓝桥杯算法提高VIP-盾神与砝码称重-题解（Java代码）

评论区

精彩推荐

WU-格式化数据输出（C++代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

1013题解

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

数字游戏（C++代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C二级辅导-温度转换（C语言代码）

上车人数（C语言代码）

青年歌手大奖赛_评委会打分（C语言代码）

Chaim

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

【偶数求和】 （C++代码）

九宫重排 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

人见人爱A+B （C语言代码）

【详细】蓝桥杯算法提高VIP-盾神与砝码称重-题解（Java代码）

评论区

精彩推荐

WU-格式化数据输出 （C++代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

1013题解

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

数字游戏 （C++代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C二级辅导-温度转换 （C语言代码）

上车人数 （C语言代码）

青年歌手大奖赛_评委会打分 （C语言代码）

【偶数求和】（C++代码）

九宫重排（C++代码）

　　评论区

WU-格式化数据输出（C++代码）

数字游戏（C++代码）

C二级辅导-温度转换（C语言代码）

上车人数（C语言代码）

青年歌手大奖赛_评委会打分（C语言代码）