Dada una array arr[] de (N – 1) enteros y cada valor arr[i] ( indexación basada en 1 ) es la puntuación de los Nodes que tienen el grado i . La tarea es determinar la puntuación máxima de cualquier árbol de N Nodes que se pueda construir.
Ejemplos:
Entrada: arr[] = {1, 3, 0}
Salida: 8
Explicación:
Una forma posible de construir un árbol es:
1
/ \
2 3
\
4
El Node 1 tiene grado 2. Por lo tanto, su puntuación es 3.
El Node 2 tiene grado 1. Por lo tanto, su puntaje es 1.
El Node 3 tiene grado 2. Por lo tanto, su puntaje es 3.
El Node 4 tiene grado 1. Por lo tanto, su puntaje es 1.
Por lo tanto, el puntaje total = 3 + 1 + 3 + 1 = 8 .Entrada: arr[] = {0, 1}
Salida: 1
Explicación:
Una forma posible de construir un árbol es:
1
/ \
2 3 El
Node 1 tiene grado 2. Por lo tanto, su puntuación es 1.
El Node 2 tiene grado 1. Por lo tanto, su puntaje es 0.
El Node 3 tiene grado 1. Por lo tanto, su puntaje es 0.
Por lo tanto, puntaje total = 1 + 0 + 0 = 1.
Enfoque ingenuo: el enfoque más simple es generar todas las combinaciones posibles para construir un árbol que tenga N Nodes y encontrar la puntuación total para cada uno de ellos. Luego, imprime el máximo de todas las puntuaciones obtenidas.
Complejidad de tiempo: (¡N!) donde N es el número de Nodes en el árbol.
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la programación dinámica mediante la creación de una tabla dp[][] donde dp[i][j] representa la puntuación máxima utilizando i Nodes que tienen la suma de los grados de los Nodes como j . Siga los pasos a continuación para resolver el problema:
- Inicialice una array dp[N + 1][2*(N – 1) + 1] donde N es el número de Nodes y (2*(N – 1)) es la suma máxima de grados.
- Inicialice dp[0][0] con 0 .
- Iterar dos bucles anidados, uno sobre el rango [1, N] y otro hasta la puntuación máxima posible 2*(N – 1) desde 1 y para cada puntuación s en el rango [1, N] atravesar la array dada de puntúa arr[] y actualiza dp[i][s] como:
dp[i][s] = max(dp[i][s], puntuaciones[j-1] dp[i-1][sj])
donde dp[i][s] representa la puntuación máxima del árbol que tiene i Nodes y suma de grados como s .
- Para un árbol con N vértices y (N – 1) aristas, la suma de todos los grados debe ser 2 * (N – 1) . Por lo tanto, imprima el valor de dp[N][2*(N – 1)] como la puntuación máxima para un árbol con N Nodes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum score
// for one possible tree having N nodes
// N - 1 Edges
int maxScore(vector<int>& arr)
{
int N = arr.size();
// Number of nodes
N++;
// Initialize dp[][]
vector<vector<int> >
dp(N + 1, vector<int>(2 * N,
-100000));
// Score with 0 vertices is 0
dp[0][0] = 0;
// Traverse the nodes from 1 to N
for (int i = 1; i <= N; i++) {
// Find maximum scores for
// each sum
for (int s = 1;
s <= 2 * (N - 1); s++) {
// Iterate over degree of
// new node
for (int j = 1; j <= N - 1
and j <= s;
j++) {
// Update the current
// state
dp[i][s]
= max(dp[i][s],
arr[j - 1]
+ dp[i - 1][s - j]);
}
}
}
// Return maximum score for N node
// tree having 2(N - 1) sum of degree
return dp[N][2 * (N - 1)];
}
// Driver Code
int main()
{
// Given array of scores
vector<int> arr = { 1, 3, 0 };
// Function Call
cout << maxScore(arr);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the maximum score
// for one possible tree having N nodes
// N - 1 Edges
static int maxScore(int[] arr)
{
int N = arr.length;
// Number of nodes
N++;
// Initialize dp[][]
int [][] dp = new int[N + 1][2 * (N - 1) + 1];
// Score with 0 vertices is 0
dp[0][0] = 0;
// Traverse the nodes from 1 to N
for(int i = 1; i <= N; i++)
{
// Find maximum scores for
// each sum
for(int s = 1; s <= 2 * (N - 1); s++)
{
// Iterate over degree of
// new node
for(int j = 1; j <= N - 1 && j <= s; j++)
{
// Update the current
// state
dp[i][s] = Math.max(dp[i][s],
arr[j - 1] +
dp[i - 1][s - j]);
}
}
}
// Return maximum score for N node
// tree having 2(N - 1) sum of degree
return dp[N][2 * (N - 1)] - 1;
}
// Driver Code
public static void main(String[] args)
{
// Given array of scores
int [] arr = { 1, 3, 0 };
// Function Call
System.out.print(maxScore(arr));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach # Function to find the maximum score # for one possible tree having N nodes # N - 1 Edges def maxScore(arr): N = len(arr) # Number of nodes N += 1 # Initialize dp[][] dp = [[-100000 for i in range(2 * N)] for i in range(N + 1)] # Score with 0 vertices is 0 dp[0][0] = 0 # Traverse the nodes from 1 to N for i in range(1, N + 1): # Find maximum scores for # each sum for s in range(1, 2 * (N - 1) + 1): # Iterate over degree of # new node j = 1 while j <= N - 1 and j <= s: # Update the current # state dp[i][s] = max(dp[i][s], arr[j - 1] + dp[i - 1][s - j]) j += 1 # Return maximum score for N node # tree having 2(N - 1) sum of degree return dp[N][2 * (N - 1)] # Driver Code if __name__ == '__main__': # Given array of scores arr = [ 1, 3, 0 ] # Function Call print(maxScore(arr)) # This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
class GFG{
// Function to find the
// maximum score for one
// possible tree having N
// nodes N - 1 Edges
static int maxScore(int[] arr)
{
int N = arr.Length;
// Number of nodes
N++;
// Initialize [,]dp
int [,] dp = new int[N + 1,
2 * (N -
1) + 1];
// Score with 0 vertices
// is 0
dp[0, 0] = 0;
// Traverse the nodes from
// 1 to N
for(int i = 1; i <= N; i++)
{
// Find maximum scores for
// each sum
for(int s = 1;
s <= 2 * (N - 1); s++)
{
// Iterate over degree of
// new node
for(int j = 1;
j <= N - 1 && j <= s; j++)
{
// Update the current
// state
dp[i, s] = Math.Max(dp[i, s],
arr[j - 1] +
dp[i - 1,
s - j]);
}
}
}
// Return maximum score for
// N node tree having 2(N - 1)
// sum of degree
return dp[N, 2 * (N -
1)] - 1;
}
// Driver Code
public static void Main(String[] args)
{
// Given array of scores
int [] arr = {1, 3, 0};
// Function Call
Console.Write(maxScore(arr));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum score
// for one possible tree having N nodes
// N - 1 Edges
function maxScore(arr)
{
var N = arr.length;
// Number of nodes
N++;
// Initialize dp[][]
var dp = Array.from(Array(N+1), ()=> Array(2*N).fill(-10000000));
// Score with 0 vertices is 0
dp[0][0] = 0;
// Traverse the nodes from 1 to N
for (var i = 1; i <= N; i++) {
// Find maximum scores for
// each sum
for (var s = 1;
s <= 2 * (N - 1); s++) {
// Iterate over degree of
// new node
for (var j = 1; j <= N - 1
&& j <= s;
j++) {
// Update the current
// state
dp[i][s]
= Math.max(dp[i][s],
arr[j - 1]
+ dp[i - 1][s - j]);
}
}
}
// Return maximum score for N node
// tree having 2(N - 1) sum of degree
return dp[N][2 * (N - 1)];
}
// Driver Code
// Given array of scores
var arr = [1, 3, 0];
// Function Call
document.write( maxScore(arr));
</script>
8
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA