首页 > 代码库 > 初级硬币最大最小问题递推法
初级硬币最大最小问题递推法
static int* Min;static int* Max;void LeastCoin2(int* Value, int Len, int *d, int Goal) { for(int i = 1; i <= Goal; i++) { for(int j = 0; j < Len; j++) { if(i >= Value[j]) { int distance = i - Value[j]; int temp1 = Min[distance] + 1; int temp2 = Max[distance] + 1; Min[i] = Min[i] < temp1 ? Min[i] : temp1; Max[i] = Max[i] > temp2 ? Max[i] : temp2; } } }}void WLeastCoin2(int* Value, int Len, int Goal) { int* d = new int [Goal+1]; if(d == NULL) { printf("malloc fail \n"); } memset(d, -1, sizeof(int)*(Goal+1)); d[0] = 0; printf("goal: %d\n", Goal); Min = new int [Goal+1]; for(int i = 0; i < Goal+1; i++) { Min[i] = 1<<10; //不能太大,防止溢出 } Min[0] = 0; Max = new int [Goal+1]; memset(Max, 0, sizeof(int)*(Goal+1)); LeastCoin2(Value, Len, d, Goal); for(int i = 0; i <= Goal; i++) { printf("%d ", Min[i]);//Min[Goal] Min } printf("\n"); for(int i = 0; i <= Goal; i++) { printf("%d ", Max[i]);//Max[Goal] Max } printf("\n");}
初级硬币最大最小问题递推法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。