Сделайте группы счастливее в поездке

Опубликовано: 5 Января, 2022

Поездка в мистическую страну будет организована в ByteLand, городе Байт. К сожалению, количество мест ограничено, например A, и N групп людей. В каждой группе может быть старик o , ребенок c , мужчина m и женщина w . Организационный комитет хочет, чтобы поездка приносила максимум удовольствия. Ценность путешествия - это сумма значений счастья всех собирающихся групп. Группа отправится в поездку, если каждый участник сможет получить место (разбивать группу - нехорошо).

Счастье ребенка c = 4
Счастье женщины w = 3
Счастье человека m = 2
Счастье старика o = 1

Счастье группы G, H (G) = (сумма счастья людей в ней) * (количество человек в группе).
Счастье группы ('coow') = (4 + 1 + 1 + 3) * 4 = 36.

Учитывая группы и общую вместимость, задача состоит в том, чтобы максимизировать счастье и напечатать максимальное счастье групп, отправляющихся в поездку.

Примеры:

Input: groups[] = {“mmo”, “oo”, “cmw”, “cc”, “c”}, A = 5
Output: 43
Pick these groups [‘cmw’, ‘cc’] to get the maximum profit of (4 + 2 + 3) * 3 + (4 + 4) * 2 = 43
Input: groups[] = {“ccc”, “oo”, “cm”, “mm”, “wwo”}, A = 10
Output: 77

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: Задачу можно рассматривать как небольшую модификацию задачи о ранце 0-1. Общее количество мест можно рассматривать как размер рюкзака. Счастье каждой группы можно рассматривать как прибыль от каждого предмета, а количество людей в каждой группе можно рассматривать как вес каждого предмета. Теперь, аналогично подходу динамического программирования для задачи о рюкзаке 0-1, примените здесь динамическое программирование, чтобы получить максимальное удовольствие.

Ниже представлена реализация описанного выше подхода:

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 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 prolem
        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 goup
            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 prolem
        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 goup
            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

Выход:

43 год

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter Олимпиады по программированию

Сделайте группы счастливее в поездке

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C ++

Джава

Python3

C #

РЕКОМЕНДУЕМЫЕ СТАТЬИ