查找总共最接近或等于给定数字的5个元素

Question

我需要一些提示来找到一个算法，返回总和最接近或等于给定数字的5元素。

这些元素的数字大于0，并且在尝试获取给定数字时每个元素只应使用1次。

比方说，我们得到了一个数组{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}和我们试图获得的数字21。它应该返回{2, 3, 4, 5, 7}。

任何帮助，非常感谢！

Answer 1

ok n loops all begin with counts = 0 (in this case n = 5) 
all loops end at MainArraySize (in this case MainArraySize = 10) 

int RequiredSum = ValueOfRequiredSum; 
int CurrentSum = 0; 
int CurrentClosestSum = 0; 
int[] Finalindexesrequired = int[5]{0,0,0,0,0}; 

//U might want to add Duplicates 
duplicate_count ++; 
int[5][] FinalindexesRequiredDuplicates= new int[5][]; 


for(int loopcount1 = 0, loopcount1++, loopcount < MainArraySize-1) 
{ 
for(int loopcount2 = 0, loopcount2++, loopcount < MainArraySize-1) 
{.. 
.. 
.. 
for(int loopcount5 = 0, loopcount5++, loopcount < MainArraySize-1) 
{ 

------------------------------------- 
Now this is all inside the 5th loop 
//Process logic here 
//Looping for first time 
if(CurrentSum = 0) 
{Currentsum = MainArray[loopcount1] + MainArray[loopcount2] + .... + MainArray[loopcount5] 
CurrentClosestSum = CurrentSum 
FinalindexesRequired[0] = loopcount1; 
FinalindexesRequired[1] = loopcount2; 
.. 
.. 
FinalindexesRequired[4] = loopcount2; 
} 

Currentsum = MainArray[loopcount1] + MainArray[loopcount2] + .... + MainArray[loopcount5] 


if((RequiredSum - CurrentSum) < (RequiredSum - CurrentClosestSum)) 
{ 
//Am gonna change the indexes because the currentsum ITERATION is closer 
FinalindexesRequired[0] = loopcount1; 
FinalindexesRequired[1] = loopcount2; 
.. 
.. 
FinalindexesRequired[4] = loopcount2; 

//If u wanted the duplicates also, since u came to a fresher ITERATION 
Reset the duplicatecount to 0 and remove all duplicates because they aint valid anymore 
} 

//What u Might want to Add is this 
if((Requiredsum - CurrentSum) = (RequiredSum - CurrentCosestSum)) 
{ 
//Hey we got Duplicates 
duplicate_count ++; 
FinalindexesRequiredDuplicates[0][duplicate_count] = loopcount1; 
FinalindexesRequiredDuplicates[1][duplicate_count] = loopcount1; 
.. 
.. 
FinalindexesRequiredDuplicates[5][duplicate_count] = loopcount1; 
} 

} 



-------------------------------- End of 5th loop 
}}}}} 



//FINALLY AFTER EXITING I THINK U HAVE UR ANSWER IN 

MAINARRAY[FINALINDEXESREQUIRED[0]] 
MAINARRAY[FINALINDEXESREQUIRED[1]] 
MAINARRAY[FINALINDEXESREQUIRED[2]] 
MAINARRAY[FINALINDEXESREQUIRED[3]] 
MAINARRAY[FINALINDEXESREQUIRED[4]] 


//IN CASE OF DUPLICATES U HAVE UR ANSWER IN 
set 1: 
MAINARRAY[FINALINDEXESREQUIRED[0]] 
MAINARRAY[FINALINDEXESREQUIRED[1]] 
MAINARRAY[FINALINDEXESREQUIRED[2]] 
MAINARRAY[FINALINDEXESREQUIRED[3]] 
MAINARRAY[FINALINDEXESREQUIRED[4]] 

other sets: 
MAINARRAY[FinalindexesRequiredDuplicates[0][0...n]] 
MAINARRAY[FinalindexesRequiredDuplicates[1][0...n]] 
MAINARRAY[FinalindexesRequiredDuplicates[2][0...n]] 
MAINARRAY[FinalindexesRequiredDuplicates[3][0...n]] 
MAINARRAY[FinalindexesRequiredDuplicates[4][0...n]] 

Answer 2

如果目标是21，为什么不能将其返回{2,3,4,5,7}，而不是{2,3,4,5,6}？ 很混乱...

如果我的理解是正确的，这个问题可以通过DP来解决。这与knap-sack问题非常相似。时间复杂度为O（n * S），其中n是数组的大小，S是您的目标。