华为OD机考题(HJ41 称砝码)

前言

经过前期的数据结构和算法学习，开始以OD机考题作为练习题，继续加强下熟练程度。有需要的可以同步练习下。

描述

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

注：称重重量包括 0

数据范围：每组输入数据满足 1≤𝑛≤10 1≤n≤10  ， 1≤𝑚𝑖≤2000 1≤mi​≤2000  ， 1≤𝑥𝑖≤10 1≤xi​≤10 

输入描述：

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

输出描述：

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

示例1

输入：

2
1 2
2 1
输出：
5
说明：可以表示出0，1，2，3，4五种重量。 

实现原理

1.按砝码重量和砝码个数存放对应数字

2.定义HashSet，用于不同重量去重，并填充0.

3.第一个砝码至最后个砝码开始计算，保存该砝码重量计算前的已支持的重量。

4.分别计算当前砝码不同个数下的重量+历史已计算出现的重量。并填充进HashSet。

实现代码

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int num=in.nextInt();int[] weights=new int[num];int[] quantity=new int[num];for(int i=0;i<num;i++){weights[i]=in.nextInt();}for(int i=0;i<num;i++){quantity[i]=in.nextInt();}Set<Integer> set=new HashSet<Integer>();set.add(0);for(int i=0;i<num;i++){List<Integer> curr=new ArrayList(set);for(int j=1;j<=quantity[i];j++){for(int k=0;k<curr.size();k++){set.add(curr.get(k)+weights[i]*j);}}}System.out.println(set.size());}
}

1.QA: