首页 > 代码库 > 初级硬币问题
初级硬币问题
已知，有一批不同面值的硬币，没有硬币个数限制，求得到S的所有组合，以及最小，最大硬币个数。
最小、最大硬币个数可以用贪心法，但是不一定能够得到有效解，但是可以提高结题速度，此处略。
下面的解法比求解最大、最小硬币比较耗时。
static int* set;static int Min = 1<<10;static int Max = 0;void LeastCoin(int* Value, int Len, int Goal, int cur) { if(Goal == 0) { for(int i = 0; i < cur; i++) { printf("%d ", set[i]); } if(cur > Max) { Max = cur; } if(Min > cur) { Min = cur; } 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(Value, Len, Goal - Value[i], cur + 1); } } } }}void WLeastCoin(int* Value, int Len, int Goal) { printf("goal: %d\n", Goal); set = new int [Len]; memset(set, 0 , sizeof(int)*Len); int cur = 0; LeastCoin(Value, Len, Goal, cur); printf("Max:%d \n", Max); printf("Min:%d \n", Min);}
初级硬币问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。