c - 合計が指定された数に最も近いか等しい配列内の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,6}ではなく{2,3,4,5,7}を返さないのはなぜですか？とても紛らわしい...

私の理解が正しければ、この問題はDPによって解決できます。これは、ナップサックの問題と非常によく似ています。時間計算量はO（n * S）です。ここで、nは配列のサイズ、Sはターゲットです。