
正文
给定一个实数数组,按序排列(从小到大),从数组从找出若干个数,使得这若干个数的和与M最为接近,描述一个算法,并给出算法的复杂度。
提示:扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
有N个正实数(注意是实数,大小升序排列) x1 , x2 ... xN,另有一个实数M。 需要选出若干个x,使这几个x的和与 M 最接近。 请描述实现算法,并指出算法复杂度。
#define M 8#define N 20int minDif = INT_MAX;vector<int> minvct;void findCloestNums(int* arr, int step, int len, vector<int> vct, int goalSum,int curSum) {if (!arr || len < 0) {return;}if (minDif > abs(curSum - goalSum)) {minDif = abs(curSum - goalSum);minvct = vct;if (minDif == 0) {return;}}if (step > len) {return;}vct.push_back(arr[step]);findCloestNums(arr, step + 1, len, vct, goalSum, curSum + arr[step]);vct.pop_back();findCloestNums(arr, step + 1, len, vct, goalSum, curSum);}







