华师一附中OI组

标题: 砝码称重问题 [打印本页]
作者: diggersun    时间: 2015-10-31 20:50
标题: 砝码称重问题
本帖最后由 diggersun 于 2015-10-31 21:00 编辑

有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    时间: 2015-10-31 20:50
本帖最后由 diggersun 于 2015-11-1 23:25 编辑
  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];//若不能用到这个砝码

  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];

  26.     return 0;
  27. }
  28. </p>
复制代码
作者: diggersun    时间: 2015-11-1 23:27
扩展思考：
1、要是1克 7克 5克3克9克的砝码分别是1,3,2,5,4个，那么能不能称出X克的重量？
2、要是5克和3克的砝码不能同时使用，能否称出X克的重量？



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2