关键理解:每次拿某个重量的砝码数与之前的所有重量数组合-穷举

称砝码

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

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList<Integer> gList = new ArrayList<>(n);
        ArrayList<Integer> numList = new ArrayList<>(n);

        for (int i = 0; i < n; i++) {
            gList.add(in.nextInt());
        }
        for (int i = 0; i < n; i++) {
            numList.add(in.nextInt());
        }

        HashSet<Integer> hashSet = new HashSet<>();
        // 重量0
        hashSet.add(0);
        for (int i = 0; i < gList.size(); i++) {
            // 重量
            Integer g = gList.get(i);

            // 拿出砝码对应的数量
            Integer num = numList.get(i);

            // 总的重量组合
            ArrayList<Integer> gNum = new ArrayList<>(hashSet);
            for (int j = 0; j < gNum.size(); j++) {
                for (Integer k = 1; k <= num; k++) {
                    hashSet.add(gNum.get(j) + (g * k));
                }
            }
        }

        System.out.println(hashSet.size());
    }
}

全部评论

相关推荐

点赞 评论 收藏
分享
大叔叔1:你把自己说的话打码,所以你想表达什么
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务