c++ - 使用递归从子集总和中找到最大总和

Question

我只想打印子集总和中的最大总和。我实际上想要的是比较函数中的所有子集总和值，然后在主函数中只返回最大总和。

我尝试做的是将子集总和值保存在一个新数组中。然后比较那里的值。但我无法做到这一点，因为它什么也没返回。 我想假设输入 array 大小是 n = 5，要求和的元素数量 是 r = 3 和数组是:

{1,2,3,4,5}

那么最大和应该是3 + 4 + 5 = 12。但我的代码返回所有的总和。

我想将求和值保存在 newArray 中

newArray[] = sum;

然后从新数组中找到最大值。

这是我的代码:

#include <stdio.h>
#include <iostream>
using namespace std;

void combinationRecursion(int start, int end, int index, int r, int *arr, int *data, int sum){

if(r == index){
    for(int i=0; i<r; i++){
        int val = data[i];
        cout<<val<<' ';
        sum = sum + data[i];

    }
    printf("sum %d\n",sum);
    printf("\n");

}
for(int i=start; i<end; i++){
    data[index] = arr[i];
    combinationRecursion(i+1, end, index+1, r, arr, data, sum);
   }
 }

 int main() {
     int arr[100], n, data[100], r;
     scanf("%d%d",&n,&r);

for(int i=0; i<n; i++) {
    scanf("%d",&arr[i]);
}
combinationRecursion(0, n, 0, r, arr, data, 0);
}

Answer 1

如果您对大小为 k 且基数为 n 的子集 感兴趣，则无需执行以下任何操作组合一代的东西。您可以按递减顺序 对数组进行排序，然后选择顶部的 k 元素，因为它们按递减顺序排序，它们将给出大小子集的最大总和 k.