Maximizar la felicidad de los grupos en el Viaje

Se va a organizar un viaje a la tierra mística en ByteLand, la ciudad de Bytes. Desafortunadamente, hay asientos limitados, digamos A y hay un número N de grupos de personas. Cada grupo puede tener anciano o , niño c , hombre m y mujer w . El comité organizador quiere maximizar el valor de felicidad del viaje. El valor de felicidad del viaje es la suma del valor de felicidad de todos los grupos que van. Un grupo irá para el viaje si cada miembro puede conseguir un asiento (Dividir un grupo no es algo bueno). 

  1. La felicidad del niño c = 4
  2. La felicidad de la mujer w = 3
  3. La felicidad del hombre m = 2
  4. La felicidad del anciano o = 1

La felicidad del grupo G, H(G) = (suma de la felicidad de las personas en él) * (número de personas en el grupo). 
La felicidad del grupo (‘coow’) = (4 + 1 + 1 + 3) * 4 = 36.
Dados los grupos y la capacidad total de asientos, la tarea es maximizar la felicidad e imprimir la felicidad maximizada de los grupos que van . en el viaje.
Ejemplos: 

Entrada: grupos[] = {“mmo”, “oo”, “cmw”, “cc”, “c”}, A = 5 
Salida: 43 
Elija estos grupos [‘cmw’, ‘cc’] para obtener el máximo ganancia de (4 + 2 + 3) * 3 + (4 + 4) * 2 = 43
Entrada: grupos[] = {“ccc”, “oo”, “cm”, “mm”, “wwo”}, A = 10 
Salida: 77 
 

Enfoque: El problema puede considerarse como una ligera modificación del problema de la mochila 0-1 . El total de asientos disponibles se puede considerar como el tamaño de la mochila. La felicidad de cada grupo se puede considerar como la ganancia de cada artículo y el número de personas en cada grupo se puede considerar como el peso de cada artículo. Ahora, similar al enfoque de programación dinámica para el problema de la mochila 0-1, aplique la programación dinámica aquí para obtener la máxima felicidad.
A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximized happiness
int MaxHappiness(int A, int N, vector<string> v)
{
    string str;
 
    // Two arrays similar to
    // 0 1 knapsack problem
    int val[N], wt[N], c = 0;
    for (int i = 0; i < N; i++) {
        str = v[i];
 
        // To store the happiness
        // of the current group
        c = 0;
        for (int j = 0; str[j]; j++) {
 
            // Current person is a child
            if (str[j] == 'c')
                c += 4;
 
            // Woman
            else if (str[j] == 'w')
                c += 3;
 
            // Man
            else if (str[j] == 'm')
                c += 2;
 
            // Old person
            else
                c++;
        }
 
        // Group's happiness is the sum of happiness
        // of the people in the group multiplied by
        // the number of people
        c *= str.length();
        val[i] = c;
        wt[i] = str.length();
    }
 
    // Solution using 0 1 knapsack
    int k[N + 1][A + 1];
    for (int i = 0; i <= N; i++) {
        for (int w = 0; w <= A; w++) {
            if (i == 0 || w == 0)
                k[i][w] = 0;
            else if (wt[i - 1] <= w)
                k[i][w] = max(val[i - 1]
                                  + k[i - 1][w - wt[i - 1]],
                              k[i - 1][w]);
            else
                k[i][w] = k[i - 1][w];
        }
    }
    return k[N][A];
}
 
// Driver code
int main()
{
 
    // Number of seats
    int A = 5;
 
    // Groups
    vector<string> v = { "mmo", "oo", "cmw", "cc", "c" };
    int N = v.size();
    cout << MaxHappiness(A, N, v);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
    // Function to return the maximized happiness
    static int maxHappiness(int A, int N, String[] v)
    {
        String str;
 
        // Two arrays similar to
        // 0 1 knapsack problem
        int[] val = new int[N];
        int[] wt = new int[N];
        int c = 0;
        for (int i = 0; i < N; i++)
        {
            str = v[i];
 
            // To store the happiness
            // of the current group
            c = 0;
            for (int j = 0; j < str.length(); j++)
            {
                // Current person is a child
                if (str.charAt(j) == 'c')
                    c += 4;
 
                // Woman
                else if (str.charAt(j) == 'w')
                    c += 3;
 
                // Man
                else if (str.charAt(j) == 'm')
                    c += 2;
 
                // Old Person
                else
                    c++;
            }
 
            // Group's happiness is the sum of happiness
            // of the people in the group multiplie
            // the number of people
            c *= str.length();
            val[i] = c;
            wt[i] = str.length();
        }
 
        // Solution using 0 1 knapsack
        int[][] k = new int[N + 1][A + 1];
        for (int i = 0; i <= N; i++)
        {
            for (int w = 0; w <= A; w++)
            {
                if (i == 0 || w == 0)
                    k[i][w] = 0;
                else if (wt[i - 1] <= w)
                {
                    k[i][w] = Math.max(val[i - 1]+ k[i - 1][w - wt[i - 1]], k[i-1][w]);
                }
                else
                {
                    k[i][w] = k[i - 1][w];
                }
            }
        }
        return k[N][A];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Number of seats
        int A = 5;
 
        // Groups
        String[] v = { "mmo", "oo", "cmw", "cc", "c" };
        int N = v.length;
        System.out.println(maxHappiness(A, N, v));
    }
}
 
// This code is contributed by Vivek Kumar Singh

Python3

# Python3 implementation of the approach
import numpy as np
 
# Function to return the maximized happiness
def MaxHappiness(A, N, v) :
     
    # Two arrays similar to
    # 0 1 knapsack problem
    val = [0] * N; wt = [0] * N; c = 0;
     
    for i in range(N) :
        string = v[i];
 
        # To store the happiness
        # of the current group
        c = 0;
        for j in range(len(string)) :
 
            # Current person is a child
            if (string[j] == 'c') :
                c += 4;
 
            # Woman
            elif (string[j] == 'w') :
                c += 3;
 
            # Man
            elif (string[j] == 'm') :
                c += 2;
 
            # Old person
            else :
                c += 1;
 
        # Group's happiness is the sum of happiness
        # of the people in the group multiplied by
        # the number of people
        c *= len(string);
         
        val[i] = c;
         
        wt[i] = len(string);
 
    # Solution using 0 1 knapsack
    k = np.zeros((N + 1, A + 1))
     
    for i in range(N + 1) :
         
        for w in range(A + 1) :
            if (i == 0 or w == 0) :
                k[i][w] = 0;
            elif (wt[i - 1] <= w) :
                k[i][w] = max(val[i - 1] +
                                k[i - 1][w - wt[i - 1]],
                                k[i - 1][w]);
            else :
                k[i][w] = k[i - 1][w];
                 
    return k[N][A];
 
# Driver code
if __name__ == "__main__" :
 
    # Number of seats
    A = 5;
 
    # Groups
    v = [ "mmo", "oo", "cmw", "cc", "c" ];
     
    N = len(v);
    print(MaxHappiness(A, N, v));
     
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
 
class GFG
{
    // Function to return the maximized happiness
    static int maxHappiness(int A, int N,
                              String[] v)
    {
        String str;
 
        // Two arrays similar to
        // 0 1 knapsack problem
        int[] val = new int[N];
        int[] wt = new int[N];
        int c = 0;
        for (int i = 0; i < N; i++)
        {
            str = v[i];
 
            // To store the happiness
            // of the current group
            c = 0;
            for (int j = 0; j < str.Length; j++)
            {
                // Current person is a child
                if (str[j] == 'c')
                    c += 4;
 
                // Woman
                else if (str[j] == 'w')
                    c += 3;
 
                // Man
                else if (str[j] == 'm')
                    c += 2;
 
                // Old Person
                else
                    c++;
            }
 
            // Group's happiness is the sum of happiness
            // of the people in the group multiplie
            // the number of people
            c *= str.Length;
            val[i] = c;
            wt[i] = str.Length;
        }
 
        // Solution using 0 1 knapsack
        int[ , ] k = new int[N + 1, A + 1];
        for (int i = 0; i <= N; i++)
        {
            for (int w = 0; w <= A; w++)
            {
                if (i == 0 || w == 0)
                    k[i, w] = 0;
                else if (wt[i - 1] <= w)
                {
                    k[i, w] = Math.Max(val[i - 1]+
                                       k[i - 1, w - wt[i - 1]],
                                       k[i - 1, w]);
                }
                else
                {
                    k[i, w] = k[i - 1, w];
                }
            }
        }
        return k[N, A];
    }
 
    // Driver code
    public static void Main()
    {
        // Number of seats
        int A = 5;
 
        // Groups
        String[] v = { "mmo", "oo", "cmw", "cc", "c" };
        int N = v.Length;
        Console.WriteLine(maxHappiness(A, N, v));
    }
}
 
// This code is contributed by Mohit kumar 29

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to return the maximized happiness
    function maxHappiness(A, N, v) {
     
        let str;
 
        // Two arrays similar to
        // 0 1 knapsack problem
        let val = Array.from({length: N}, (_, i) => 0);
        let wt = Array.from({length: N}, (_, i) => 0);
        let c = 0;
        for (let i = 0; i < N; i++)
        {
            str = v[i];
 
            // To store the happiness
            // of the current group
            c = 0;
            for (let j = 0; j < str.length; j++)
            {
                // Current person is a child
                if (str[j] == 'c')
                    c += 4;
 
                // Woman
                else if (str[j] == 'w')
                    c += 3;
 
                // Man
                else if (str[j] == 'm')
                    c += 2;
 
                // Old Person
                else
                    c++;
            }
 
            // Group's happiness is the sum of happiness
            // of the people in the group multiplie
            // the number of people
            c *= str.length;
            val[i] = c;
            wt[i] = str.length;
        }
 
        // Solution using 0 1 knapsack
        let k = new Array(N + 1);
        for (var i = 0; i < k.length; i++) {
            k[i] = new Array(2);
        }
         
        for (let i = 0; i <= N; i++)
        {
            for (let w = 0; w <= A; w++)
            {
                if (i == 0 || w == 0)
                    k[i][w] = 0;
                else if (wt[i - 1] <= w)
                {
                    k[i][w] = Math.max(val[i - 1]+ k[i - 1][w - wt[i - 1]], k[i-1][w]);
                }
                else
                {
                    k[i][w] = k[i - 1][w];
                }
            }
        }
        return k[N][A];
    }
 
 
// Driver Code
 
    // Number of seats
        let A = 5;
 
        // Groups
        let v = [ "mmo", "oo", "cmw", "cc", "c" ];
        let N = v.length;
        document.write(maxHappiness(A, N, v));
 
// This code is contributed by sanjoy_62.
</script>
Producción: 

43

 

Publicación traducida automáticamente

Artículo escrito por Azad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *