现有一组砝码，重量互不相等，分别为m1、m2……mn；

他们可取的最大数量分别为x1、x2……xn。

现在要用这些砝码去称物体的重量，问能称出多少中不同的重量。

注：

称重重量包括0

要对输入数据进行校验

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

输入：int n：n表示有多少组重量不同的砝码，n不大于10

int[] weight：表示n组砝码的重量

int[] num：表示n组砝码的最大数量

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

例 输入 2 1 2 2 1

输出 5

---

 

以下来自旭东的博客，权作个人笔记

http://www.cnblogs.com/xudong-bupt/archive/2013/03/17/2964909.html

　　砝码称重问题:设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其质量<=1000g），求出用他们能称出的质量的种类数(不包括质量为0的情况)。

　　一、动态规划方法求解

　　设dp[1000]数组为标记数组。当dp[i]=0时，表示质量为i的情况，目前没有称出；当dp[i]=1时，表示质量为i的情况已经称出。

　　本题目中有多个砝码，我们顺序处理每一个砝码。

　　当处理第j个砝码，质量为wj时，有下列推导公式：

　　　　　　　　　　　　　　　　

　　完整程序代码如下：

#include
       
        #include
        
         int sum;  ///表示输入的砝码的总质量int ma[6];  ///六种砝码的个数int weight[6]={1,2,3,5,10,20};  ///六种砝码的重量char dp[1001]; ///标记位void input();   ///输入每个砝码的数量，并求出所有砝码的总质量sumvoid exeDP();void output();  ///判断标记为1的数量，并输出int main(){    memset(dp,0,sizeof(dp));    input();    exeDP();    output();    return 0;}void input(){    int i;    sum=0;    for(i=0;i<6;i++)    {        scanf("%d",&ma[i]);        sum=sum+(ma[i]*weight[i]);    }}void exeDP(){    int i,j,z;    dp[0]=1;    for(i=0;i<6;i++)    ///六种砝码    {        for(j=0;j
         
          =weight[i];z--) ///判断每种质量是否可以被称出            {                if(dp[z-weight[i]]==1)                    dp[z]=1;            }        }    }}void output(){    int i,time=0;    for(i=1;i<=sum;i++)    {        if(dp[i]==1)    ///若能被称出，则计数            time++;    }    printf("%d",time);}
         
        
       

　　二、母函数求解

　　设输入的质量为w的砝码n个，则可以用母函数表示为:

　　针对本题目，例如输入六种砝码（1g,2g,3g,5g,10g,20g）的个数分别为：1,2,2,0,0,1。则有：

　　用matlab软件的符号计算有：

>> syms x;>> f1=(1+x);>> f2=(1+x^2+x^4);>> f3=(1+x^3+x^6);>> f4=(1+x^20);>> expand(f1*f2*f3*f4) >>ans= x^31 + x^30 + x^29 + 2*x^28 + 2*x^27 + 2*x^26 + 2*x^25 + 2*x^24 + 2*x^23 + x^22 + x^21 + x^20 + x^11 + x^10 + x^9 + 2*x^8 + 2*x^7 + 2*x^6 + 2*x^5 + 2*x^4 + 2*x^3 + x^2 + x + 1

　　其中x的指数就是能够称出的质量，可知可以称出的不同质量个数为23个。

---