Java机试题*：称砝码（完全搜索、组合问题、set去重、要考虑全面思路要正确）

本文主要是介绍Java机试题*：称砝码（完全搜索、组合问题、set去重、要考虑全面思路要正确），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

描述

现有一组砝码，重量互不相等，分别为 m1,m2,m3…mn ；
每种砝码对应的数量为 x1,x2,x3...xn 。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。

 

注：

称重重量包括 0    本题有多组输入   数据范围：每组输入数据满足  ，  ， 

输入描述：

输入包含多组测试数据。
对于每组测试数据：
第一行：n --- 砝码数(范围[1,10])
第二行：m1 m2 m3 ... mn --- 每个砝码的重量(范围[1,2000])
第三行：x1 x2 x3 .... xn --- 每个砝码的数量(范围[1,6])

输出描述：

利用给定的砝码可以称出的不同的重量数

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



public class Main {
    /**
     * 思路： 根据砝码重量和个数，遍历出所有个数情况下的重量，利用set去重
     * 遍历的思路：
     * 思路1：根据所取出的砝码个数组合，0个到砝码个数和。
     * 思路2：将每种砝码自身可以组合的重量存为一组结果，然后一组一种的组合过去。这里使用思路二
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            // 获取砝码以及对应的个数
            int numw = sc.nextInt();
            List<Weights> weights = new ArrayList<Weights>();
            for (int i = 0; i < numw; i++) {
                Weights wei = new Weights();
                wei.setWeight(sc.nextInt());
                weights.add(wei);
            }
            for (int i = 0; i < weights.size(); i++) {
                weights.get(i).setNum(sc.nextInt());
            }
            // 根据数量获取所有的砝码
            // 利用hashSet不能重复的特点,找出所有可称的重量
            // 思路2：将每种砝码自身可以组合的重量存为一联，然后一联一联吃过去。
            Set<Integer> ret = new HashSet<Integer>();
            // 初始化0
            ret.add(0);
            // 遍历每种砝码
            for (int i = 0; i < weights.size(); i++) {
                int num = weights.get(i).getNum();
                int weight = weights.get(i).getWeight();
                // 已找到的所有重量，有0
                List<Integer> weightRets = new ArrayList<Integer>(ret);
                while(num > 0) {
                    for (int j = 0; j < weightRets.size(); j++) {
                        // 取该砝码一个到num个，与前面的重量组合填充
                        ret.add(weightRets.get(j) + weight * num);
                    }
                    num--;
                }
                // 该砝码自己本身也是一个重量，需要放在与之前重量组合之后，否则会多算
                ret.add(weight);
            }
            System.out.println(ret.size());
        }
    }

    
}

class Weights {
    private int weight;
    
    private int num;

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }
}

题目来源：牛客网

这篇关于Java机试题*：称砝码（完全搜索、组合问题、set去重、要考虑全面思路要正确）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！