题目描述：公司发了某商店的购物券1000元，限定只能购买店中的m种商品。每种商品的价格分别为m1,m2,.....，要求程序列出所有的正好能消费完该购物券的不同购物方法。
程序输入：
第一行是一个整数m，代表可购买的商品的种类数。
接下来是m个整数，每个一行，分别代表着m种商品的单价
程序输出：
第一行是一个整数，表示共有多少种方案。
第二行开始，每种方案占一行，表述对每种商品购买的数量，中间用空格分隔。
例如：
输入：
2
200
300
则应输出：
2
2 2
5 0
----题目出自 第二届全国软件专业人才设计与开发大赛 选拔赛
我的代码如下：
#include <stdio.h>
#include <conio.h>
#define SUM_MONEY 1000
#define MAX 1000
//global variables
int m=0;//the number of the kinds
int price[MAX]={0};//the price of all the kinds
int num[MAX]={0};//the max number of one kind good
int count=1;//the number of methods
int c_sum=0;//current sum price
int result[MAX][MAX]={0};//the result number of each kind good
//int visited[MAX]={0};
//prototypes
void back_money(int n);//n is the number of plies
int main()
{
int i=0;
printf("Please input the number of the goods:");
scanf("%d",&m);
for(i=1;i<=m;i++)
{
printf("Please input the price of %d: ",i);
scanf("%d",&price[i]);
num[i]=SUM_MONEY/price[i];
}
back_money(1);
printf("the number is :%d\n",count-1);
for(i=1;i<count;i++)
{
for(int x=1;x<=m;x++)
{
printf("%d ",result[i][x]);
}
printf("\n");
}
getch();
}
void back_money(int n)//n is the number of plies
{
int j=1;
if(c_sum==SUM_MONEY)
{
count++;
for(int temp=1;temp<=m;temp++)
result[count][temp]=result[count-1][temp];
return ;
}
if(n>m)
return;
for(j=0;j<=num[n];j++)
{
if(c_sum+price[n]<=SUM_MONEY)
{
//visited[j]=1;
c_sum+=price[n]*j;
result[count][n]=j;
back_money(n+1);
result[count][n]=0;
//visited[j]=0;
c_sum-=price[n]*j;
}
}
}