华为机试-称砝码

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

注： 称重重量包括0

方法原型：public static int fama(int n, int[] weight, int[] nums)

输入描述: 输入包含多组测试数据。

对于每组测试数据：

第一行：n — 砝码数(范围[1,10])

第二行：m1 m2 m3 … mn — 每个砝码的重量(范围[1,2000])

第三行：x1 x2 x3 …. xn — 每个砝码的数量(范围[1,6])

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

输入例子: 2 1 2 2 1

输出例子: 5 注意：因为称重量包括0，所以才为5。

---

思路：输入砝码种类n; 输入砝码质量w[i]; 输入砝码个数c[i]； 输出 可以拼凑的质量个数 w1 w2 w3 w4 …… wn c1 c2 c3 c4 …… cn对于前i个砝码：（不同质量为Q[i])则 Q[i]=Q[i-1]+k*w[i]; –>0<=k<=c[i]; Q[i]在Q[i-1]的基础上，对Q[i-1]个不同的重量，分别添加k个砝码i; 在添加的过程中去除重复情况 c[i]表示N个不同砝码相应的数量 c[1~~n]; 则（结果）:Q[i]=(Q[i-1]+k*w[i])–(减去)添加过程中重复的个数。

---

代码；

---

import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Scanner; public class Fama { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); while (sc.hasNext()) { int n=sc.nextInt(); int weight[]=new int[n]; int[] nums=new int[n]; for(int i=0;i<n;i++) { weight[i]=sc.nextInt(); } for(int i=0;i<n;i++) { nums[i]=sc.nextInt(); } System.out.println(fama(n, weight, nums)); } } public static int fama(int n,int weight[],int nums[]) { HashSet<Integer> myset=new HashSet<Integer>(); for(int i=0;i<=nums[0];i++) { myset.add(i*weight[0]); } for(int i=1;i<n;i++) { List<Integer> list=new ArrayList<Integer>(myset); for(int j=1;j<=nums[i];j++) { for(int k=0;k<list.size();k++) { myset.add(list.get(k)+j*weight[i]); } } } return myset.size(); } }