Prüfen Sie, ob eine Zielsumme bei gegebenem Wertevektor möglich ist
Posted: 23 Jan 2025, 07:26
Das Problem besteht darin, zu prüfen, ob es möglich ist, eine bestimmte Zielsumme aus den Elementen eines bestimmten Arrays zu erhalten. Jedes Element sollte nur einmal enthalten sein (sofern enthalten).
Der Code ist ein Brute-Force-Ansatz mit Rekursion. Ich wollte die Idee umsetzen, dass true zurückgegeben wird, wenn das aktuelle Element die Summe gleich targetSum macht. Wenn das aktuelle, zu currSum hinzugefügte Element kleiner als targetSum ist, prüfen Sie, ob die Einbeziehung des Elements „true“ zurückgibt. Wenn ja, gebe ich true zurück, andernfalls überprüfe ich, ohne es in currSum aufzunehmen.
Die Sache ist, dass das Programm für einige Vektoren eine korrekte Antwort gibt, und a Falsche Antwort für einige andere Vektoren.
Die rekursive Funktion:
Für diese Eingabe:
Die Ausgabe ist falsch.
Für diese Eingabe:
Die Ausgabe ist wahr.
Ich kann nicht herausfinden, was hier möglicherweise schief läuft.
Der Treibercode:
Der Code ist ein Brute-Force-Ansatz mit Rekursion. Ich wollte die Idee umsetzen, dass true zurückgegeben wird, wenn das aktuelle Element die Summe gleich targetSum macht. Wenn das aktuelle, zu currSum hinzugefügte Element kleiner als targetSum ist, prüfen Sie, ob die Einbeziehung des Elements „true“ zurückgibt. Wenn ja, gebe ich true zurück, andernfalls überprüfe ich, ohne es in currSum aufzunehmen.
Die Sache ist, dass das Programm für einige Vektoren eine korrekte Antwort gibt, und a Falsche Antwort für einige andere Vektoren.
Die rekursive Funktion:
Code: Select all
bool checkSum(vector v, int idx, int currSum, int targetSum){
if(idx == v.size()) return false;
if(currSum+v[idx] == targetSum) return true;
if(currSum+v[idx] > targetSum) return false;
bool ans = checkSum(v, idx+1, currSum+v[idx], targetSum);
if(ans) return true;
ans = checkSum(v, idx+1, currSum, targetSum);
return ans;
}
Code: Select all
v : [ 4 18 5 9 ]
targetSum : 14
Für diese Eingabe:
Code: Select all
v : [ 4 11 5 9 ]
targetSum : 14
Ich kann nicht herausfinden, was hier möglicherweise schief läuft.
Der Treibercode:
Code: Select all
int main(){
int n;
cin>>n;
vector v(n);
for(auto &it:v){
cin>>it;
}
int targetSum;
cin>>targetSum;
cout