华为OJ之放砝码

xuesn

　　题目描述：
　　现有一组砝码，重量互不相等，分别为m1、m2……mn；他们可取的最大数量分别为x1、x2……xn。现在要用这些砝码去称物体的重量，问能称出多少中不同的重量。
　　注：
　　称重重量包括0；
　　要对输入数据进行校验
　　方法原型：public static int fama(int n, int[] weight, int[] nums)
　　题目分析：
　　1，遇到这种问题我们最容易想到的解决思路应该就是穷举法了，实际上穷举法是大多数算法的实现基础，只不过优秀的算法能够根据之前已经计算出的部分结果来对以后的计算进行剪枝或者简化计算罢了。这里我们也利用穷举算法来解决；
　　2，不过对于穷举法来说，最大的制约在于两点：穷举的时空开销和穷举本身的难度。我们暂不考虑复杂度的问题，由于事先并不清楚砝码的种类个数，因此无法用传统的多重循环来遍历所有的可能情况,。这里我给大家提供一个思路，基本上对于类似的穷举问题都是通用的；
　　3，让我们这样考虑，总共的放置方法totalConditions = (num[0] + 1) * (num[1] + 1) * ... * (num[num.length - 1] + 1)，注意砝码个数可以为零；
　　我们构建一个位数为weight.length的数，从左至右依次为重量为weight[0], weight[1], ... 的砝码的个数，那么这实际上是一个可变进制的n位数，从左至右进制依次为(num[0] + 1), (num[0] + 1), ...
　　因此我们对数字进行0到(totalConditions - 1)的遍历，便可根据这个数字计算出对应的各种砝码的个数，从而得到称重重量，进而我们用一个HashSet来存放结果，最后HashSet的Size便是结果数了。
　　具体代码(Java实现)：



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

public class Weight {
     public static void main(String[] args) {
         
         @SuppressWarnings("resource")
         Scanner reader = new Scanner(System.in);
         int num = reader.nextInt();
         int[] weight = new int[num];
         int[] nums = new int[num];
         for (int i = 0; i < num; i ++) {
             reader.nextLine();
             weight = reader.nextInt();
         }
         for (int i = 0; i < num; i ++) {
             reader.nextLine();
             nums = reader.nextInt();
         }
         getResultCount(num, weight, nums);
         
     }
     
     public static void getResultCount(Integer num, int[] weight, int[] nums) {
         HashSet<Integer> results = new HashSet<Integer>();
         int caseCount = 1;
         for (int i = 0; i < nums.length; i ++) {
             caseCount *= (nums + 1);
         }
         int[] specificCase = new int[num];
         for (int i = 0; i < caseCount; i ++) {
             int l = i;
             for (int j = 0; j < num; j ++) {
                 specificCase[num - j - 1] = l % (nums[num - j - 1] + 1);
                 l = l / (nums[num - j - 1] + 1);
             }
             results.add(calculate(weight, specificCase));
         }
         System.out.println(results.size());
     }
     
     public static int calculate(int[] weight, int[] specificCase) {
         
         int weights = 0;
         for (int i = 0; i < weight.length; i ++) {
             weights = weights + weight * specificCase;
         }
         return weights;
     }

}