Beneficio máximo tal que el valor total robado sea inferior a K para obtener la bonificación

Posted on by Rudeus Greyrat

Dado un número entero K y una array arr[] que denota la cantidad que se puede robar, la tarea es elegir un subconjunto de artículos de modo que su valor total sea menor que K para obtener la cantidad de bonificación. 

Monto de la bonificación: El monto de la bonificación será el valor máximo que se puede robar del conjunto de artículos por cada artículo robado. 
Monto de bonificación = (Máx. de arr[]) * (Número de artículos robados) 
 

Ejemplos:  

Entrada: arr[] = {1, 2, 3, 4, 5}, K = 7 
Salida: 22 
Explicación: 
El valor máximo que se puede robar es – 5. 
Si los artículos fueron robados son 1, 2 y 4. Entonces el la suma total del valor robado será menor que K. 
Por lo tanto, Beneficio total 
=> valor de cada artículo + valor máximo que se puede robar 
=> 1 + 5 + 2 + 5 + 4 + 5 = 22 

Entrada: arr[] = {5, 2, 7, 3}, K = 6 
Salida: 19 
Explicación: 
El valor máximo que se puede robar es – 7 
Si los artículos robados son 2 y 3. Entonces la suma total del valor robado será menos que K. 
Por lo tanto, Beneficio total 
=> Valor de cada artículo + Valor máximo que se puede robar 
=> 2 + 7 + 3 + 7 = 19 

Enfoque: La idea es usar permutación y combinaciones para elegir los elementos de manera que su suma total sea menor que K. Por lo tanto, considerar todo lo posible resultará en el máximo beneficio posible.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation to find the
// maximum stolen value such that
// total stolen value is less than K
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find the maximum
// profit from the given values
int maxProfit(vector<int> value,
                         int N, int K)
{
    sort(value.begin(), value.end());
    int maxval = value[N - 1];
    int maxProfit = 0;
    int curr_val;
     
    // Iterating over every
    // possible permutation
    do {
        curr_val = 0;
        for (int i = 0; i < N; i++) {
            curr_val += value[i];
            if (curr_val <= K) {
                maxProfit = max(curr_val +
                  maxval * (i + 1), maxProfit);
            }
        }
    } while (next_permutation(
        value.begin(), value.end()));
    return maxProfit;
}
 
// Driver Code
int main()
{
    int N = 4, K = 6;
    vector<int> values{5, 2, 7, 3};
     
    // Function Call
    cout << maxProfit(values, N, K);
}

Java

// Java implementation to find the
// maximum stolen value such that
// total stolen value is less than K
import java.util.*;
class GFG{
  
// Function to find the maximum
// profit from the given values
static int maxProfit(int []value,
                     int N, int K)
{
    Arrays.sort(value);
    int maxval = value[N - 1];
    int maxProfit = 0;
    int curr_val;
      
    // Iterating over every
    // possible permutation
    do {
        curr_val = 0;
        for (int i = 0; i < N; i++) {
            curr_val += value[i];
            if (curr_val <= K) {
                maxProfit = Math.max(curr_val +
                                     maxval * (i + 1),
                                     maxProfit);
            }
        }
    } while (next_permutation(value));
    return maxProfit;
}
static boolean next_permutation(int[] p) {
      for (int a = p.length - 2; a >= 0; --a)
        if (p[a] < p[a + 1])
          for (int b = p.length - 1;; --b)
            if (p[b] > p[a]) {
              int t = p[a];
              p[a] = p[b];
              p[b] = t;
              for (++a, b = p.length - 1; a < b; ++a, --b) {
                t = p[a];
                p[a] = p[b];
                p[b] = t;
              }
              return true;
            }
      return false;
    }
   
// Driver Code
public static void main(String[] args)
{
    int N = 4, K = 6;
    int []values = {5, 2, 7, 3};
      
    // Function Call
    System.out.print(maxProfit(values, N, K));
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 implementation to find the
# maximum stolen value such that
# total stolen value is less than K
 
# Function to find the maximum
# profit from the given values
def maxProfit(value, N, K):
     
    value.sort()
    maxval = value[N - 1]
    maxProfit = 0
     
    # Iterating over every
    # possible permutation
    while True:
        curr_val = 0
        for i in range(N):
            curr_val += value[i]
             
            if (curr_val <= K):
                maxProfit = max(curr_val + maxval *
                                      (i + 1), maxProfit)
                                       
        if not next_permutation(value):
            break
     
    return maxProfit
 
def next_permutation(p):
     
    for a in range(len(p) - 2, -1, -1):
        if p[a] < p[a + 1]:
            b = len(p) - 1
             
            while True:
                if p[b] > p[a]:
                    t = p[a]
                    p[a] = p[b]
                    p[b] = t
                     
                    a += 1
                    b = len(p) - 1
                     
                    while a < b:
                        t = p[a]
                        p[a] = p[b]
                        p[b] = t
                         
                        a += 1
                        b -= 1
                         
                    return True
                     
                b -= 1
     
    return False
     
# Driver Code 
N, K = 4, 6
values = [ 5, 2, 7, 3 ]
 
# Function Call
print(maxProfit(values, N, K))
 
# This code is contributed by divyesh072019

C#

// C# implementation to find the
// maximum stolen value such that
// total stolen value is less than K
using System;
 
class GFG{
     
// Function to find the maximum
// profit from the given values
static int maxProfit(int[] value,
                     int N, int K)
{
    Array.Sort(value);
    int maxval = value[N - 1];
    int maxProfit = 0;
    int curr_val;
       
    // Iterating over every
    // possible permutation
    do
    {
        curr_val = 0;
        for(int i = 0; i < N; i++)
        {
            curr_val += value[i];
            if (curr_val <= K)
            {
                maxProfit = Math.Max(curr_val +
                                     maxval * (i + 1),
                                     maxProfit);
            }
        }
    } while (next_permutation(value));
    return maxProfit;
}
 
static bool next_permutation(int[] p)
{
    for(int a = p.Length - 2; a >= 0; --a)
        if (p[a] < p[a + 1])
            for(int b = p.Length - 1;; --b)
                if (p[b] > p[a])
                {
                    int t = p[a];
                    p[a] = p[b];
                    p[b] = t;
                       
                    for(++a, b = p.Length - 1;
                            a < b; ++a, --b)
                    {
                        t = p[a];
                        p[a] = p[b];
                        p[b] = t;
                    }
                    return true;
                }
    return false;
}
 
// Driver code  
static void Main()
{
    int N = 4, K = 6;
    int[] values = { 5, 2, 7, 3 };
   
    // Function call
    Console.WriteLine(maxProfit(values, N, K));
}
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
 
    // Javascript implementation to find the
    // maximum stolen value such that
    // total stolen value is less than K
     
    // Function to find the maximum
    // profit from the given values
    function maxProfit(value, N, K)
    {
        value.sort();
        let maxval = value[N - 1];
        let maxProfit = 0;
        let curr_val;
 
        // Iterating over every
        // possible permutation
        do
        {
            curr_val = 0;
            for(let i = 0; i < N; i++)
            {
                curr_val += value[i];
                if (curr_val <= K)
                {
                    maxProfit = Math.max(curr_val +
                                         maxval * (i + 1),
                                         maxProfit);
                }
            }
        } while (next_permutation(value));
        return maxProfit;
    }
 
    function next_permutation(p)
    {
        for(let a = p.length - 2; a >= 0; --a)
            if (p[a] < p[a + 1])
                for(let b = p.length - 1;; --b)
                    if (p[b] > p[a])
                    {
                        let t = p[a];
                        p[a] = p[b];
                        p[b] = t;
 
                        for(++a, b = p.length - 1;
                                a < b; ++a, --b)
                        {
                            t = p[a];
                            p[a] = p[b];
                            p[b] = t;
                        }
                        return true;
                    }
        return false;
    }
     
    let N = 4, K = 6;
    let values = [ 5, 2, 7, 3 ];
    
    // Function call
    document.write(maxProfit(values, N, K));
 
</script>
Producción: 

19

 

Tiempo Complejidad: O(N 2 ) 
Espacio auxiliar: O(N)
 

Publicación traducida automáticamente

Artículo escrito por yatinagg 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 *