购物券消费方案

购物券消费方案

时间： 1ms        内存：128M

描述：

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

输入：

第一行是一个整数m，代表可购买的商品的种类数。

接下来是m个整数，每个1行，分别代表这m种商品的单价(0<m<1000)。

输出：

第一行是一个整数，表示共有多少种方案

第二行开始，每种方案占1行，表示对每种商品购买的数量，中间用空格分隔。

示例输入：

2
200
300

示例输出：

2
2  2
5  0

提示：

参考答案（内存最优[1100]）：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int m,ma;
int a[109];
int b[109];
int ans=0;
int num[109],k=0;

void pan(){
    int s=0,i;
    for(i=1;i<=m;i++){
        s+=a[i]*num[i];
    }
    if(s==1000)ans++;
    else return ;
    for(i=1;i<=m;i++){
        b[k++]=num[i];
    }
}

void f(int k){
    int i,j;
    if(k==m+1){
        pan();
    }
    else{
        for(i=0;i<=ma;i++)
        {
            num[k]=i;
            f(k+1);
        }
    }
}

int main(){
    //freopen("f.txt","r",stdin);
    scanf("%d",&m);
    int i,mi=1006;
    for(i=1;i<=m;i++){
    scanf("%d",&a[i]);
    mi=min(a[i],mi);
    }
    ma=1000/mi;
    memset(b,0,sizeof(b));
    f(1);
    printf("%d\n",ans);
    for(i=0;i<k;i++){
        if((i+1)%m==0)printf("%d\n",b[i]);
        else printf("%d  ",b[i]);
    }
}

参考答案（时间最优[0]）：

#include <iostream>
#include <cstring>
#include <cstdio>
#define MAXMONEY 1000
using namespace std;
int HOWMANY2[1000]={0};
int end2[1000][1000]={0};
char pri2[1000][1000];
int k2=0;
int cost2[1000]={0};
int count2;
int n2;
int main()
{
	int comp(const void*a,const void*b);
	void dfs(int);
	cin>>n2;
	int i,j;
	int money=MAXMONEY;
	for(i=0;i<n2;i++)
	{
		cin>>cost2[i];
	}
	count2=0;
	dfs(money);
	int s1=0;
	int y,z;
    char temp[1000];
	for(y=0;y<count2-1;y++)
    {
        for(z=y+1;z<count2;z++)
        {
            if(strcmp(pri2[y],pri2[z])<0)
            {
                strcpy(temp,pri2[y]);
                strcpy(pri2[y],pri2[z]);
                strcpy(pri2[z],temp);
            }
        }
    }
	for(i=0;i<count2;i++)
	{
		if(i==0||strcmp(pri2[i-1],pri2[i])!=0)
		{
		for(j=n2-1;j>=0;j--)
		{
			end2[s1][j]=int(pri2[i][j]);
		}
		s1++;
		}
	}
	cout<<s1<<endl;
	for(i=s1-1;i>=0;i--)
	{
		for(j=0;j<n2-1;j++)
		{
			cout<<end2[i][j]<<"  ";
		}
		cout<<end2[i][j]<<endl;
	}
	return 0;
}
void dfs(int money)
{
	int i;
	for(i=0;i<n2;i++)
	{
		if(money-cost2[i]>0)
		{
			HOWMANY2[i]++;
			dfs(money-cost2[i]);
			HOWMANY2[i]--;
		}
		else
		{
			if(money-cost2[i]==0)
			{
				HOWMANY2[i]++;
				int j;
				for(j=0;j<n2;j++)
				{
					pri2[k2][j]=HOWMANY2[j];
				}
				pri2[k2][j]='\0';
				k2++;
				count2++;
				HOWMANY2[i]--;
			}
		}
	}
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。