c语言求一升序数组求不超过某数M的最大元素和

c语言求一升序数组求不超过某数M的最大元素和

#include 
#include 
#include 

int max(int a, int b) {
return a > b ? a : b;
}

int maxsum(int array[], int index, int num, int M) {
if (M == 0) return 0;
if (index == num) return 0;
if (array[index] > M) return 0;
if (array[index] == M) return M;
return max(maxsum(array, index + 1, num, M), array[index] + maxsum(array, index + 1, num, M - array[index]));
}

int main() {
int a[4] = { 1, 2, 5, 8 };
int M = 7;
printf("%d
", maxsum(a, 0, 4, M));
} 
比较暴力，没有剪枝
追问- -！忘了说了，是double的数组。。。。大神麻烦改下了⊙﹏⊙‖追答#include 
#include 
#include 

double max(double a, double b) {
return a > b ? a : b;
}

double maxsum(double array[], int index, int num, double M) {
if (M == 0) return 0;
if (index == num) return 0;
if (array[index] > M) return 0;
if (array[index] == M) return M;
return max(maxsum(array, index + 1, num, M), array[index] + maxsum(array, index + 1, num, M - array[index]));
}

int main() {
double a[4] = { 1, 2, 5, 8 };
double M = 7;
printf("%d
", maxsum(a, 0, 4, M));
}

先找到最后一个不大于M的数。然后从两侧开始，找出两数之和sum≤M的数，如当前值大于之前的sum找将sum重新赋值。追问不是俩数之和，可以随便选数量的。。。比如{1,1,5,8,}，M=7，就选1,1,5追答如果只要找一个解还简单，若是找所有那这个就要动态规划了追问求教做人！⊙﹏⊙