1564.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

//#define debug 0
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 30000
#define NMAX 13
int n,t;
int a[NMAX];
int m[NMAX];
int l[NMAX];
int diff;
int f[NMAX];
int next[NMAX];
bool yes;

int len[5000];
typedef struct
{
	int r[12];
	int len;
}data;
data ans[5000];
int cp=0;
int cmp(const void *a,const void *b)
{
	return (*(int*)b)-(*(int*)a);
}
void input()
{
	int i;
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	qsort(a,n,sizeof(int),cmp);
	m[0]=a[0];
	l[0]=1;
	int k=1;
	for(i=1;i<n;i++)
	{
		if(a[i]!=a[i-1])
		{
			m[k]=a[i];
			l[k]=1;
			k++;
		}
		else
		{
			l[k-1]++;
		}
	}
	diff=k;
}
void output()
{
	int i,j;
	yes=1;
	int k=0;
	for(i=0;i<diff;i++)
	{
		if(!f[i])
			continue;
		for(j=1;j<=f[i];j++)
		{
			ans[cp].r[k++]=m[i];
		}
	}
	ans[cp].len=k;
	cp++;
	
}
void tr(int i,int last)
{
	int k;
	if(last==0)
	{
		output();
		return ;
	}
	if(i>=diff)
		return ;
	for(k=0;k<=l[i];k++)
	{
		if(last-k*m[i]>=0)
		{
			f[i]=k;
			tr(i+1,last-k*m[i]);
			f[i]=0;
		}
		else
			break;
	}


}
int cmp2(const void *a,const void *b)
{
	
	int tr=((data*)b)->r[0]-((data*)a)->r[0];
	if(tr)
		return tr;
//	int tl=((data*)a)->len-((data*)b)->len;
//	if(tl)
//		return tl;
	for(int i=0;i<((data*)a)->len;i++)
	{
		tr=((data*)b)->r[i]-((data*)a)->r[i];
		if(tr)
		{
			return tr;
		}
	}
}
void solve()
{
	printf("Sums of %d:\n",t);
	yes=0;
	cp=0;
	tr(0,t);
	if(!yes)
		printf("NONE\n");
	qsort(ans,cp,sizeof(data),cmp2);
	for(int i=0;i<cp;i++)
	{
		printf("%d",ans[i].r[0]);
		for(int j=1;j<ans[i].len;j++)
			printf("+%d",ans[i].r[j]);
		printf("\n");
	}

	
}
int main()
{

#if _DEBUG	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	while(1)
	{
		scanf("%d%d",&t,&n);
		memset(f,0,sizeof(f));
		if(!t)
			break;
		input();
		solve();
	}
#if _DEBUG
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}