HJ41 称砝码

Love The Way You Lie 2024-03-27 13:56 96阅读 0赞

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ]  
> [牛客在线编程算法篇【题号NC开头】][NC]  
> [剑指offer【题号 JZ开头】][offer_ JZ]  
> [力扣][Link 1]

### 1）[原题链接][Link 2] ###

### 2）已有题解 ###

### 3）代码 ###

package dfs;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    import java.util.HashSet;
    
    import static java.lang.Integer.parseInt;
    import static java.lang.System.in;
    
    /**
     * HJ41 称砝码
     */
    public class HJ41WeightIndication {
        
        public static void main(String[] args) throws IOException {
        
            BufferedReader bf = new BufferedReader(new InputStreamReader(in));
            // n种砝码
            int n = parseInt(bf.readLine());
            // 每种砝码重量
            Integer[] weights = Arrays.stream(bf.readLine().split(" ")).limit(n).map(Integer::parseInt).toArray(Integer[]::new);
            // 每种几个
            Integer[] nums = Arrays.stream(bf.readLine().split(" ")).limit(n).map(Integer::parseInt).toArray(Integer[]::new);
            bf.close();
    
            HashSet<Integer> allCase = getWeights(n, weights, nums);
    
            System.out.println(allCase.size());
        }
    
        /**
         * @param kinds     n种砝码
         * @param weightPer 每种砝码重量
         * @param countPer  每种几个
         */
        private static HashSet<Integer> getWeights(int kinds, Integer[] weightPer, Integer[] countPer) {
        
            // 所有砝码重量组合情况set
            HashSet<Integer> allCase = new HashSet<>();
    
            // 由示例可知，0重量也属于一种情况
            allCase.add(0);
    
            for (int i = 0; i < kinds; i++) {
         //每一种砝码
                HashSet<Integer> curKindWeights = new HashSet<>();
    
                for (int k = 1; k <= countPer[i]; k++) {
         // 每种砝码遍历每个
                    int stepWeight = weightPer[i] * k; // 砝码个数叠加枚举
                    curKindWeights.add(stepWeight);
    
                    for (Integer weight : allCase) {
        
                        curKindWeights.add(weight + stepWeight);
                    }
                }
    
                allCase.addAll(curKindWeights);
            }
    
            return allCase;
        }
    }

[HJ]: https://www.nowcoder.com/exam/oj/ta?tpId=37
[NC]: https://www.nowcoder.com/exam/oj
[offer_ JZ]: https://www.nowcoder.com/exam/oj/ta?page=1&tpId=13&type=13
[Link 1]: https://leetcode.cn/problemset/all/
[Link 2]: https://www.nowcoder.com/practice/f9a4c19050fc477e9e27eb75f3bfd49c?tpId=37&tqId=21264&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=/exam/oj/ta?tpId=37&difficulty=undefined&judgeStatus=undefined&tags=&title=