有N个正实数(注意是实数,大小升序排列) x1 , x2 ... xN,另有一个实数M。 需要选出若干个x,使这几个x的和与 M 最接近。 请描述实现算法,并指出算法复杂度。
#define M 8 #define N 20 int 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); }