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).
- La felicidad del niño c = 4
- La felicidad de la mujer w = 3
- La felicidad del hombre m = 2
- 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>
43