程公司发了某商店的购物券1000元，限定只能购买店中的m种商品。每种商品的价格分别为m1,m2,…，要求程序列出所有的正好能消费完该购物券的不同购物方法。序输入：第一行是一个整数m，

Question

程公司发了某商店的购物券1000元，限定只能购买店中的m种商品。每种商品的价格分别为m1,m2,…，要求程序列出所有的正好能消费完该购物券的不同购物方法。
序输入：
第一行是一个整数m，代表可购买的商品的种类数。
接下来是m个整数，每个1行，分别代表这m种商品的单价。
程序输出：
第一行是一个整数，表示共有多少种方案
第二行开始，每种方案占1行，表示对每种商品购买的数量，中间用空格分隔。
例如：
输入：
2
200
300
则应输出：
2

Answer 1

　　#include
　　#include
　　int *a,*b;
　　//int c[20000];
　　int n;
　　int count = 0;
　　void print()
　　{
　　int i;
　　for(i = 0; i < n; i++)
　　printf("%d ",b[i]);
　　printf("\n");
　　}
　　void problem9(int total,int size)
　　{
　　if(size != n )
　　{
　　if(total == 0)//判断背包是否正装满
　　{
　　count++;//存放可行方案的个数
　　print();//输出此可行解
　　}
　　else
　　{
　　problem9(total,size + 1);//未放入物品a【size】的情况
　　if(total - a[size] >= 0)//判断放入a【size】后，是否会超出背包的承载
　　{
　　b[size]++;//使得a【size】对应物品的数量加1
　　problem9(total - a[size],size);//放入物品a[size]的情况
　　b[size]--;//使得相应的物品数量减1
　　}
　　}
　　}
　　}
　　void main()
　　{
　　int i,j;
　　scanf("%d",&n);
　　a = (int*)malloc(sizeof(int) * n);
　　b = (int*)malloc(sizeof(int) * n);
　　for(i = 0; i < n; i++)
　　scanf("%d",&a[i]);
　　for(j = 0; j < n; j++)
　　b[j] = 0;
　　problem9(1000,0);
　　printf("%d",count);
　　}