购物卷1000元买多种东西，刚好用完的解决方案（C语言实现）

 

#include<stdio.h>

#define M_MAX  20//最多输入的商品种类
#define MONEY  1000//购物卷金额

int m;//商品种类
int price[M_MAX];//存储各种商品价格
int max_count[M_MAX];//每一种商品最多能买多少个
int count[M_MAX];//记录当前各个商品的个数
int remark[M_MAX*4][M_MAX];//记录符号条件的商品个数
int k=0;//记录总共有多少种解决方案

void max_count_value();//给max_count数组赋值
void calculate(int index);//递归寻找符号条件的方案
void show_answer();//显示所有方案

void main()
{
	int i;
	printf("please input m:\n");
	scanf("%d",&m);
	for(i=0;i<m;i++){
		scanf("%d",&price[i]);
	}
	max_count_value();
	calculate(0);
	show_answer();
}

//给max_count数组赋值
void max_count_value()
{
	int i,j;
	for(i=0;i<m;i++){
		for(j=0;;j++)
			if(price[i]*j>MONEY)
				break;
		max_count[i]=j-1;
	}
}

//递归寻找符号条件的方案
void calculate(int index)
{
	int i,sum=0;
    if(index==m){//递归出口
		for(i=0;i<m;i++)
			sum+=count[i]*price[i];
		if(sum==MONEY){//找到一种方案，记录下当时的各类商品个数
			for(i=0;i<m;i++)
		       remark[k][i]=count[i];
			k++;
		}
		return;
	}
    for(i=0;i<=max_count[index];i++){
		count[index]=i;
        calculate(index+1);//递归
	}
}

//显示所有方案
void show_answer()
{
	int i,j;
	printf("%d\n",k);
	for(i=0;i<k;i++){
		for(j=0;j<m;j++)
           printf("%-3d",remark[i][j]);
		printf("\n");
	}
}

 原题：