[数据结构与算法]蓝桥杯之“砝码称重“解题思路，含图解（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=5，我们可以把5和3作为新的砝码，等放入下一个砝码时，就可以在原来秤出的重量上计算新的重量

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

算法图解：

图解一：分析先放入a，再放入b，在放入c的图解

图解二：分析不放入a，再放入b，再放入c的情况

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

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

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

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

完整代码如下：

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());
    }
}

运行结果：

?当然了，本人也使用过递归爆搜的解法，时长方面肯定过不去，给有需要的读者作为参考：

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，如果读者们可以理解我这个解法当然我是最开心的，虽然在表述上没这么清晰吧，但是图解是我的全部想法，这个解法也是我自己独立想出来的，感谢您的阅读！🏃