Imprimer la solution à la somme maximale des éléments non consécutifs dans un tableau
J'essaie d'afficher les éléments dans un tableau qui totalisent un nombre maximum et aucun élément n'est consécutif (adjacent).
J'ai compris comment calculer la somme maximale en conservant une somme inclusive et exclusive des éléments du tableau. Existe-t-il un moyen optimisé de capturer tous les éléments qui constituent la somme maximale et de l'afficher dans l'ordre inverse
Code:
int i_sum = tickets[0];
int e_sum = 0;
int new_sum = 0
int sum = 0;
for (int i = 1; i < n; i++)
{
new_sum = (i_sum > e_sum) ? i_sum : e_sum;
i_sum = e_sum + tickets[i];
e_sum = new_sum;
}
(i_sum >= e_sum) ? std::cout << "incl " << i_sum : std::cout << "excl " << e_sum;
Par exemple :
n = 8
tableau = [100, -3, 200, 50, 400, -7, 20, 80]
somme max = 780
production: 80,400,200,100
Et si la somme inclusive et la somme exclusive sont identiques, la sortie sera celle avec le plus grand ensemble d'éléments.
Cas :
n = 4
tableau = [4, 5, 4, 3]
somme max = 8
sortie: 4, 4
Dois-je conserver deux tableaux différents pour contenir toutes les valeurs possibles, ou les insérer un par un à chaque passage?
Merci d'avance.
Oui, vous pouvez conserver deux baies et les copier et les échanger à chaque étape. Cependant, ce n'est pas optimal. Cela rendra votre algorithme O (n 2 ) .
std::vector<int> incl, excl;
if (tickets[0] > 0)
incl.push_back(tickets[0]);
for (int i = 1; i < n; i++)
{
std::vector<int> temp;
if (i_sum > e_sum) {
new_sum = i_sum;
} else {
new_sum = e_sum;
temp = excl;
}
i_sum = e_sum + tickets[i];
e_sum = new_sum;
excl.push_back(tickets[i]);
std::swap(incl, excl);
if (temp.size())
excl = temp;
}
inclou exclcontiendra votre solution selon la plus grande des deux.
J'ai fait une petite optimisation en utilisant std::swappour utiliser la sémantique de déplacement qui évite les copies, mais quand e_sum > i_sum, nous ne pouvons pas éviter de copier tempvers excl.
Au lieu de cela, en formulant le même problème en utilisant la programmation dynamique, vous pouvez le faire en O (n) . L'idée est similaire. Soit vous incluez l'élément actuel et ajoutez à la solution la somme maximale du deuxième élément précédent, soit vous excluez l'élément actuel pour avoir la solution de l'élément précédent. Code comme suit:
vector <int> dp(n);
vector <int> parent(n, 0);
if (tickets[0] > 0) {
dp[0] = tickets[0];
parent[0] = tickets[0];
}
if (tickets[1] > 0) {
dp[1] = tickets[1];
parent[1] = tickets[1];
}
for (int i = 2; i < n ; i++) {
if (dp[i-1] > tickets[i] + dp[i-2]) {
dp[i] = dp[i-1];
} else {
dp[i] = tickets[i] + dp[i-2];
parent[i] = tickets[i];
}
}
cout << "Max sum: " << dp[n-1] << endl;
for(int i = n - 1; i >= 0;) {
if (parent[i]) {
cout << parent[i] << ' ';
i = i - 2;
} else {
i--;
}
}
parent vector peut être utilisé pour retracer les étapes de la solution de programmation dynamique.
En passant, la solution mentionnée dans votre question est légèrement incorrecte. Si le premier élément est négatif, vous obtiendrez un résultat non optimal.