首页 > 代码库 > 硬币问题

硬币问题

不同的面值Value[ ]有硬币个数Num[ ]限制,凑齐Goal面值,需要的最小和最大个数。

static int  Min = 1<<10;static  int Max = 0;static int* set;static int* Count;void LeastCoin_N(int* Value, int* Num, int Len, int Goal, int cur) {   	if(Goal == 0) 	{		if(cur > Max)		{			for(int i = 0; i < Len; i++)			{						for(int j = 0; j < cur; j++)				{					if(Value[i] == set[j])					{						Count[i]++;						if(Count[i] > Num[i])						{							goto  initial;						}					}				}			}			for(int i = 0; i < cur; i++)			{			     printf("%d ", set[i]);  			}			Max = cur;		}		if(Min > cur)		{						for(int i = 0; i < Len; i++)			{						for(int j = 0; j < cur; j++)				{					if(Value[i] == set[j])					{						Count[i]++;						if(Count[i] > Num[i])						{							goto  initial;						}					}				}			}  					for(int i = 0; i < cur; i++)			{				printf("%d ", set[i]); 			}			        Min = cur;		}initial:			memset(Count, 0 , sizeof(int)*Len);		printf("\n");	}	else	{		for(int i = 0; i < Len; i++)		{			if(Goal >= Value[i]) 			{							        int ok = 1;				for(int j = 0; j < cur; j++)				{					if(set[j] > Value[i])					{						ok = 0;						break;					}									}				if(ok)				{									set[cur] = Value[i];  					LeastCoin_N(Value, Num, Len, Goal - Value[i], cur + 1);								}			}				}	} }int WLeastCoin_N(int* Value, int* Num, int Len,int Goal){	printf("goal: %d\n", Goal);	set = new int [Len];	memset(set, 0 , sizeof(int)*Len);	Count = new int [Len];	memset(Count, 0 , sizeof(int)*Len);	int cur = 0;	LeastCoin_N(Value, Num, Len, Goal,  cur);	printf("Max:%d \n", Max);	printf("Min:%d \n", Min);	return 0;}

  

硬币问题