砝码称重问题

diggersun

有1克 7克 5克3克9克的砝码各一个，有多少种方法可以称得出10克的重量？
这是一个最简单的背包问题，标准的做法是用一个二位数组F(x,y)表示用不超过编号为y的砝码凑出x的重量有多少方法，那么显然
f(0,y)=1 y=(0..5)  不管用多少砝码，称出0克的重量都有一种方法，这好像不用解释。
f(x,y)=f(x,y-1) 或者f(x-a(y),y-1)+f(x,y-1)     f(x,y-1)的意思是不用这个编号为y的砝码，f(x-a(y),y-1)的意思是说用这个编号为y的砝码，那么有个约束条件 x>=a(i)
更通俗的理解是说若不用编号为y的砝码，相当于用前面y-1的砝码凑出重量x，若用编号为y的砝码，就是前面y-1个砝码凑出重量x-a(y)；
程序我写了两个，一个使用二位数字F(x,y)进行很直观的递推。
第二种方法就用了一个一维数组 g(x)，从后面往前推，类似杨辉三角的做法。

diggersun

1. <p>#include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. int a[6]={0,1,7,3,5,9};  //假设有5个砝码分别是1 3 5 7 9克加个假砝码0克
   
5. int f[30][6]; //f[x][y] 表示用不超过编号为Y的砝码拼出X克的重量有多少种可能
   
6. int g[30];
   
7. int i,j;
   
8. int main()
   
9. {
   
10. //第一种方法
    
11.   </p><p>  for (i=0;i<=5;i++) f[0][i]=1;  //拼出0克显然有1种方法
    
12.     for (i=1;i<=5;i++)
    
13.         for (j=0;j<=29;j++)
    
14.            if (j>=a[i]) f[j][i]=f[j][i-1]+f[j-a[i]][i-1]; //若能用到这个砝码
    
15.            else f[j][i]=f[j][i-1];//若不能用到这个砝码
    
16. 
    
17.     for (i=1;i<=5;i++)
    
18.         {for (j=0;j<=29;j++) cout<<setw(2)<<f[j][i];
    
19.          cout<<endl;}
    
20. //第二种方法
    
21.     g[0]=1;
    
22.     for (i=1;i<=5;i++)
    
23.         for (j=29;j>=a[i];j--) g[j]=g[j]+g[j-a[i]];
    
24.     for (i=0;i<=29;i++) cout<<setw(2)<<g[i];
    
25. 
    
26.     return 0;
    
27. }
    
28. </p>

复制代码

diggersun

扩展思考：
1、要是1克 7克 5克3克9克的砝码分别是1,3,2,5,4个，那么能不能称出X克的重量？
2、要是5克和3克的砝码不能同时使用，能否称出X克的重量？