称砝码

题目描述 现有一组砝码，重量互不相等，分别为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]) 输出描述: 利用给定的砝码可以称出的不同的重量数 示例1 输入 2 1 2 2 1 输出

5

package Ray; import java.util.*; public class Farmar { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNextLine()){ int n = in.nextInt(); // n 种砝码 int weights[] = new int[n]; int nums[] = new int[n]; for(int i = 0;i<n;i++){ weights[i] = in.nextInt(); } for(int i = 0;i<n;i++){ nums[i] = in.nextInt(); } System.out.println(getNums(n, weights, nums)); } in.close(); } private static int getNums(int n, int weight[], int nums[]) { int[] m = new int[n]; int[] x = new int[n]; int sum = 0; // 总的重量 for (int i = 0; i < n; i++) { m[i] = weight[i]; // 每种砝码的重量 x[i] = nums[i]; // 每种砝码的数量 sum += x[i] * m[i]; } boolean[] temp = new boolean[sum+1]; temp[0] = true; temp[sum] = true; for (int i = 0; i < n; i++) { for (int j = 0; j < x[i]; j++) { for (int k = sum; k >= m[i]; k--) { if (temp[k - m[i]]) temp[k] = true; } } } int count = 0; for (int i = 0; i <= sum; i++) { if (temp[i]) count++; } return count; } }