公司发了某商店的购物券1000元，限定只能购买店中的m种商品。每种商品的价格分别为m1,m2,…，要求程序列出所有的正好能消费完该购物券的不同购物方法。
程序输入：
第一行是一个整数m，代表可购买的商品的种类数。
接下来是m个整数，每个1行，分别代表这m种商品的单价。
程序输出：
第一行是一个整数，表示共有多少种方案
第二行开始，每种方案占1行，表示对每种商品购买的数量，中间用空格分隔。
例如：
输入：
2
200
300
则应输出：
2
2 2
5 0
输入：
2
500
800
则应输出：
1
2 0
#include<stdio.h>
#include<string.h>
int cost;
int n;//物品个数
int price[2000];//物品单价
int num[100];//物品数目
int sum=0;//方案数目
int arg[100][100];//每种方案的商品分布
void Fun(int x)//递归,每件物品分为买或者不买的情况（同一物品可以买多次）
{
int i;
if(cost>1000||x>=n)
return;
if(cost==1000)
{
for(i=0; i<n; i++)
arg[sum][i] = num[i];
sum++;
return;
}
num[x]++;//选择这件商品的情况
cost+=price[x];
Fun(x);//还可能继续选这件商品
num[x]--;//不选择这件商品的情况
cost-=price[x];
Fun(x+1);//往下走
}
int main()
{
int i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&price[i]);
memset(num,0,sizeof(num));//数组清0为了之后的加减运算
Fun(0);
printf("%d\n",sum);
for(i=0;i<sum;i++)
{
printf("%d",arg[i][0]);//防止多输出空格
for(j=1;j<n;j++)
printf(" %d",arg[i][j]);
puts("");
}
return 0;
}
参考：http://www.cnblogs.com/hxsyl/archive/2012/12/15/2819911.html
