题解 | #称砝码#

称砝码

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

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            int[] w= new int[n];//不同种类对应重量数组
            int[] g=new int[n];//不同种类对应个数数组
            for (int i = 0; i <n; i++) {
                w[i]=scanner.nextInt();
            }
            for (int i = 0; i <n; i++) {
                g[i]=scanner.nextInt();
            }
            HashSet<Integer> hsout = new HashSet<>();//外部建立大的不重复集合
            hsout.add(0);//允许重量为0
            for (int i = 0; i <n; i++) {//  第一层循环种类,有几种就循环几次
                HashSet<Integer> hsin = new HashSet<>();//每一种在循环时得到的情况先在此存储,最后合并给外部大集合
                for (int j = 1; j <=g[i]; j++) {//  第二层循环个数,有几个就循环几次
                    int newweight = j * w[i];//个数*重量 产生新的重量可能新
                    for (int oldweight:hsout) {// 第三层循环外部大不重复集合的个数
                        hsin.add(oldweight+newweight);//取出外部大集合每一个oldweight与newweight相加,从而产生新的重量可能
                    }
                }
                hsout.addAll(hsin);//最终向外部大集合合并
            }
            System.out.println(hsout.size());
        }
    }
}

全部评论
点赞 回复 分享
发布于 05-14 16:29 北京

相关推荐

点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务