硬幣問題
來源：程序員人生 發布時間：2014-09-17 20:12:15 閱讀次數：2721次
不同的面值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("
");
}
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
", 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
", Max);
printf("Min:%d
", Min);
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
