形成具有特殊约束的数组子集

Question

我最近在编码竞赛中遇到了这个问题：我们必须与成员组成一个技能小队，使得没有一个成员的技能超过小队中任何其他两个成员的技能总和。给定 n 个成员的技能数组，找出在上述约束条件下可能的小队技能的最大总和。我使用了贪心算法： - 对数组进行排序； - 使用三个指针并选择索引，使得前两个元素（最小）的总和小于所考虑子数组的最后一个（最大元素）。 -同时继续移动索引以检查所有此类子数组和 return 其中的最大总和。但这通过了一半的案例，而其他案例则失败了。有人可以帮我解决我在这里缺少的东西吗？以下是我的程序：

//Author:: Satish Srinivas
#include<bits/stdc++.h>

using namespace std;

int solve(int arr[],int n)
{
    sort(arr,arr+n);

    int sum[n];
    sum[0]=arr[0];

    //precompute sums    
    for(int i=1;i<n;i++)
    {
        sum[i]=sum[i-1]+arr[i];

    }

    if(n<=2)
        return sum[n-1];

    int res=INT_MIN;

    for(int i=0;i<=n-3;i++)
    {
        int min=arr[i]+arr[i+1];

        int j=i+1;

        while(j<=n-2 && arr[j+1]<=min)
            j++;

        if(j>i+1)
        {
         if(i==0)
         {
            if(res < sum[j]-sum[0])
             res=sum[j]-sum[0];
         }
         else
         {
            if(res < sum[j]-sum[i-1])
             res=sum[j]-sum[i-1];
         }

        }

    }
  return res;
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
/*
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
*/
int arr1[]={10,4,4,5,4};
int n1=sizeof(arr1)/sizeof(arr1[0]);
cout<<solve(arr1,n1)<<endl;

int arr2[]={25,60,1,5,3,35};
int n2=sizeof(arr2)/sizeof(arr2[0]);
cout<<solve(arr2,n2)<<endl;

return 0;
}
//output:
//13
//120

Answer 1

一些看起来有点不对劲的地方：

如果 n 等于 2，你 return INT_MIN 因为你的 for 循环永远不会执行
更一般地说，您似乎认为规模为 2 的团队无效
当i等于0时，你想计算从i到j的所有数字相加的分数，这等于sum[j]但是你计算res=sum[j] -总和[0]
因为你已经对数组进行了排序，你实际上不需要在每次迭代中重置 j （这只在你因超时而失败时才重要）

形成具有特殊约束的数组子集

Form subset of an array with special constraints

arrays

algorithm

greedy