题解 | #称砝码#

称砝码

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

DFS练习,for循环解决问题

读入，Scanner.readLine（），转为对应的Int数组
遍历，DFS超时（学习，待改进），改用for循环，因为不能回溯，需要临时存储上一种砝码的结果

遍历每种类型的砝码
遍历该类型的每个
遍历上一类结果与之相运算并加入最终结果
需要初始化添加一个0，因为砝码称重是0，单个砝码的重量获取需要这个0

存储，Set去重
结果，set的size()

for循环遍历，100%

import java.util.*;

public class Main {
   private static Set<Integer> mCount = new HashSet<>();//可以承重的个数就是size
   private static void doFor(int [] mWeight,int[] mX ){
        mCount.add(0);
        for (int i = 0;i <mWeight.length; i++){//每个砝码自重
            HashSet<Integer> beforeSet = new HashSet<>(mCount);
            int temp = 0;
            for (int j= 1;j <= mX[i]; j++){//单个砝码总重
                temp += mWeight[i];
                //不用递归需要存储上一次的计算结果，并且在第二次时取出和本次结果相运算
                for (Integer tempC : beforeSet) {
                    mCount.add(tempC+temp);
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.valueOf(scanner.nextLine());//个数
        String[] splitM = scanner.nextLine().split(" ");//砝码重量
        String[] splitX = scanner.nextLine().split(" ");//对应砝码个数
        scanner.close();

        int[] mWeight = new int[n];
        int[] mX = new int[n];
        for (int i = 0; i < n; i++) {
            mWeight[i] = Integer.valueOf(splitM[i]);
            mX[i] = Integer.valueOf(splitX[i]);
        }
//        dfs(mWeight,mX,0);
        doFor(mWeight,mX);
        System.out.println(mCount.size());
    }
    //Main
}

双层循环递归数据大的时候超时，仅仅作为学习的参考思想，练习深度搜索，二者解决思想都是获取单砝码自重，与其他砝码组合重量，二者的并集

DFS遍历，80%

import java.util.*;

public class Main {
   private static Set<Integer> mCount = new HashSet<>();//可以承重的个数就是size
    private static boolean[] flag = new boolean[10];

    private static int tempC =0;
    private static void dfs(int [] mWeight,int[] mX ,int start){
        if (start == mWeight.length){//出口
            mCount.add(tempC);
            return;
        }
        for (int i = 0;i <mWeight.length; i++){//每个砝码自重
            if (!flag[i]){
                //
                int temp = 0;
                for (int j= 1;j <= mX[i]; j++){//单个砝码总重
                    flag[i] = true;//标记
                    temp += mWeight[i];
                        mCount.add(temp);
                        tempC += temp;
                        mCount.add(tempC);
                    dfs(mWeight,mX,start+1);//递归
                    flag[i] = false;//恢复
                        tempC -= temp;
                }
                //回溯，剪枝交给Set
            }
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.valueOf(scanner.nextLine());//个数
        String[] splitM = scanner.nextLine().split(" ");//砝码重量
        String[] splitX = scanner.nextLine().split(" ");//对应砝码个数
        scanner.close();

        int[] mWeight = new int[n];
        int[] mX = new int[n];
        for (int i = 0; i < n; i++) {
            mWeight[i] = Integer.valueOf(splitM[i]);
            mX[i] = Integer.valueOf(splitX[i]);
        }
        //0可以
        dfs(mWeight,mX,0);
        System.out.println(mCount.size()+1);
    }
    //Main
}