取数组中n个数之和为不大于目标值的最大值

admin1

1. static int getMaxNotMoreThanTarget(int a, int b, int target) {
2.                 //如果两个数都大于目标值，返回0
3.                 if (target < a && target < b) {
4.                         return 0;
5.                 }
6.                 //如果一个数大于目标值，一个数小于目标值，返回小于目标值的的数
7.                 if (target < a) {
8.                         return b;
9.                 }
10.                 if (target < b) {
11.                         return a;
12.                 }
13.                 //两个数都小于目标值返回较大值
14.                 return a > b ? a : b;
15.         }
18.         static int getSum(vector<int> array, int start) {
19.                 int sum = 0;
20.                 for (int i = start; i < array.size(); i++) {
21.                         sum += array[i];
22.                 }
23.                 return sum;
24.         }
29.         static int getSumClosestToTarget(vector<int> array, int start, int target) {
30.                 //目标值小于0，不可能有这种情况，因为工时都是正整数
31.                 if (target < 0) {
32.                         return 0;
33.                 }
34.                 //如果当前数组全部之和小于目标值直接返回
35.                 int sum = getSum(array, start);
36.                 if (sum <= target) {
37.                         return sum;
38.                 }
39.                 //取两部分较大值
40.                 return getMaxNotMoreThanTarget(getSumClosestToTarget(array, start + 1,
41.                         target - array[start]) + array[start]
42.                 , getSumClosestToTarget(array, start + 1, target)
43.                         , target);
44.         }

复制代码

admin1

1.         int target = 371;
2.                 backtrack(sssa, target, 0, 0, 0,maxSum);
4. static        void backtrack(vector<int>& nums, int target, int start, int count, int sum,int &maxSum) {
5.                 if (sum > target) {
6.                         return;
7.                 }
8.                 maxSum = max(maxSum, sum);
9.                 if (count == nums.size()) {
10.                         return;
11.                 }
12.                 for (int i = start; i < nums.size(); i++) {
13.                         sum += nums[i];
14.                         backtrack(nums, target, i + 1, count + 1, sum , maxSum);
15.                         sum -= nums[i];
16.                 }
17.         }

复制代码