硬币问题

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; }