Construya el mayor número cuya suma de costo de dígitos sea K

Posted on by Rudeus Greyrat

Dado un entero positivo K y una array arr[] que consta de N(=9) enteros tales que arr[i] representa el costo del dígito (i+1) , la tarea es encontrar el número más grande que se puede formar usando los dígitos sobre el rango [1, 9] tal que la suma del costo de los dígitos del número formado es K .

Ejemplos:

Entrada: K = 14, arr[] = {3, 12, 9, 5, 3, 4, 6, 5, 10} Salida:
8555 Explicación
:
Un número posible con costo K que se puede formar es 8555. El costo de incluir el dígito 8 es arr[7]( =5) y el dígito 5 es arr[2]( =3).
Por lo tanto, el costo total es (5+3*3 = 14). Y también el número formado 8555 es el número máximo posible con este costo.

Entrada:  K = 5, arr[] = {3, 12, 9, 5, 3, 4, 6, 5, 10} Salida:
8 Explicación
:
Un número posible con costo K que se puede formar es 8. El costo de incluir el dígito 8 es arr[7]( =5).
Por lo tanto, el costo total es (5 = 5). Y también el número formado 8 es el número máximo posible con este costo.

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:

  1. El problema es la variación del 0/1 Unbounded Knapsack ya que los dígitos elegidos para formar el mayor número también pueden repetirse y su suma de costes debe ser K .
  2. Por lo tanto, la idea es incluir o excluir cada dígito posible repetidamente para formar el número más grande e imprimir el número máximo obtenido después de todas las combinaciones posibles.
  3. La idea anterior se puede implementar de acuerdo con la siguiente relación de recurrencia :
    • Mantenga un registro del dígito utilizado para formar el número y la suma restante K en cada paso.
    • La condición base de la relación de recurrencia es:
      1. Si la suma K se convierte en 0 , entonces esto da como resultado una de las combinaciones de los números formados.
      2. Si K es negativo o se recorre todo el arreglo, entonces es imposible formar cualquier número cuya suma de costos sea K.
    • En cada paso, primero, incluya y luego excluya cualquier dígito D y llame recursivamente a la función , con el costo K restante actualizado, respectivamente.

Siga los pasos a continuación para resolver el problema dado:

  • Inicialice la array 2D , digamos dp[][] de tamaño 10*K , de modo que dp[i][j] almacene el número más grande formado al usar los primeros i dígitos que tienen la suma j .
  • Defina una función recursiva , digamos recursion(i, K) donde el índice inicial, la suma K , y realice los siguientes pasos:
    1. Definir el caso base como :
      • Si el valor de la suma K se convierte en 0 , devuelve una string vacía de la función como el número cuya suma del costo del dígito se ha formado.
      • Si el valor de la suma K es menor que 0 o i es igual a N, entonces devuelve «0» de la función ya que no se puede formar ningún número.
    2. Si el estado actual dp[i][N] ya está calculado, devuelva este valor de la función .
    3. Almacene el resultado obtenido al incluir el dígito actual i+1 como to_string(i+1) + recursion(0, K – arr[D]) en la variable, digamos include .
    4. Almacene el resultado obtenido al excluir el dígito actual i+1 como recursión (i+1, K – arr[D]) en la variable, digamos excluir.
  • Actualice el estado actual de DP dp[i][K] a max(include,exclude) y devuelva este valor de la función.
  • Después de completar los pasos anteriores, llame a la función recursiva recursion(0, K) y verifique si la string devuelta está vacía, luego imprima «0» . De lo contrario, imprima la string devuelta como el número máximo resultante formado.

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 number
// among the two numbers S and T
string getMaximum(string& S, string& T)
{
    // If "0" exists in the string S
    if (S.find("0") != string::npos)
        return T;
 
    // If "0" exists in the string T
    if (T.find("0") != string::npos)
        return S;
 
    // Else return the maximum number
    // formed
    return (S.length() > T.length() ? S : T);
}
 
// Recursive function to find maximum
// number formed such that the sum of
// cost of digits of formed number is K
string recursion(int arr[], int idx,
                 int N, int K,
                 vector<vector<string> >& dp)
{
    // Base Case
    if (K == 0) {
        return "";
    }
    if (K < 0 or idx == N) {
        return "0";
    }
 
    // Return the stored state
    if (dp[idx][K] != "-1")
        return dp[idx][K];
 
    // Including the digit (idx + 1)
    string include
        = to_string(idx + 1)
          + recursion(arr, 0, N,
                      K - arr[idx], dp);
 
    // Excluding the digit (idx + 1)
    string exclude = recursion(
        arr, idx + 1, N, K, dp);
 
    // Store the result and return
    return dp[idx][K] = getMaximum(
               include, exclude);
}
 
// Function to find the maximum number
// formed such that the sum of the cost
// digits in the formed number is K
string largestNumber(int arr[], int N, int K)
{
    // Stores all Dp-states
    vector<vector<string> > dp(
        N + 1, vector<string>(K + 1,
                              "-1"));
 
    // Recursive Call
    string ans = recursion(arr, 0, N,
                           K, dp);
 
    // Return the result
    return (ans == "" ? "0" : ans);
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 12, 9, 5, 3, 4, 6, 5, 10 };
    int K = 14;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << largestNumber(arr, N, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
public class Main
{
  // Function to find the maximum number
  // among the two numbers S and T
  static String getMaximum(String S, String T)
  {
 
    // If "0" exists in the string S
    if (S.indexOf("0") > -1) return T;
 
    // If "0" exists in the string T
    if (T.indexOf("0") > -1) return S;
 
    // Else return the maximum number
    // formed
    return S.length() > T.length() ? S : T;
  }
 
  // Recursive function to find maximum
  // number formed such that the sum of
  // cost of digits of formed number is K
  static String recursion(int[] arr, int idx, int N, int K, Vector<Vector<String>> dp)
  {
 
    // Base Case
    if (K == 0) {
      return "";
    }
    if (K < 0 || idx == N) {
      return "0";
    }
 
    // Return the stored state
    if (dp.get(idx).get(K) != "-1") return dp.get(idx).get(K);
 
    // Including the digit (idx + 1)
    String include = String.valueOf(idx + 1) + recursion(arr, 0, N, K - arr[idx], dp);
 
    // Excluding the digit (idx + 1)
    String exclude = recursion(arr, idx + 1, N, K, dp);
 
    // Store the result and return
    dp.get(idx).set(K, getMaximum(include, exclude));
    return dp.get(idx).get(K);
  }
 
  // Function to find the maximum number
  // formed such that the sum of the cost
  // digits in the formed number is K
  static String largestNumber(int[] arr, int N, int K)
  {
 
    // Stores all Dp-states
    Vector<Vector<String>> dp = new Vector<Vector<String>>();
    for(int i = 0; i < N + 1; i++)
    {
      dp.add(new Vector<String>());
      for(int j = 0; j < K + 1; j++)
      {
        dp.get(i).add("-1");
      }
    }
 
    // Recursive Call
    String ans = recursion(arr, 0, N, K, dp);
 
    // Return the result
    return ans == "" ? "0" : ans;
  }
 
  public static void main(String[] args) {
    int[] arr = {3, 12, 9, 5, 3, 4, 6, 5, 10};
    int K = 14;
    int N = arr.length;
 
    System.out.print(largestNumber(arr, N, K));
  }
}
 
// This code is contributed by decode2207.

Python3

# Python program for the above approach
 
# Function to find the maximum number
# among the two numbers S and T
def getMaximum(S, T):
 
  # If "0" exists in the string S
  if (S.count("0") > 0):
      return T;
 
  # If "0" exists in the string T
  if (T.count("0") > 0):
      return S;
 
  # Else return the maximum number
  # formed
  return S if len(S) > len(T) else T;
 
# Recursive function to find maximum
# number formed such that the sum of
# cost of digits of formed number is K
def recursion(arr, idx, N, K, dp):
 
  # Base Case
    if (K == 0):
        return "";
 
    if (K < 0 or idx == N):
        return "0";
 
    # Return the stored state
    if (dp[idx][K] != "-1"):
        return dp[idx][K];
 
    # Including the digit (idx + 1)
    include = str(idx + 1) + recursion(arr, 0, N, K - arr[idx], dp);
 
    # Excluding the digit (idx + 1)
    exclude = recursion(arr, idx + 1, N, K, dp);
 
    # Store the result and return
    dp[idx][K] = getMaximum(include, exclude)
    return (dp[idx][K])
 
 
# Function to find the maximum number
# formed such that the sum of the cost
# digits in the formed number is K
def largestNumber(arr, N, K):
 
    # Stores all Dp-states
    dp = [["-1" for i in range(K + 1)] for i in range(N + 1)]
 
    # Recursive Call
    ans = recursion(arr, 0, N, K, dp);
 
    # Return the result
    return "0" if ans == "" else ans;
 
# Driver Code
arr = [3, 12, 9, 5, 3, 4, 6, 5, 10];
K = 14;
N = len(arr);
 
print(largestNumber(arr, N, K));
 
# This code is contributed by _saurabh_jaiswal.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
     
    // Function to find the maximum number
    // among the two numbers S and T
    static string getMaximum(string S, string T)
    {
        // If "0" exists in the string S
        if (S.IndexOf("0") > -1)
            return T;
      
        // If "0" exists in the string T
        if (T.IndexOf("0") > -1)
            return S;
      
        // Else return the maximum number
        // formed
        return (S.Length > T.Length ? S : T);
    }
      
    // Recursive function to find maximum
    // number formed such that the sum of
    // cost of digits of formed number is K
    static string recursion(int[] arr, int idx, int N, int K, List<List<string>> dp)
    {
        // Base Case
        if (K == 0) {
            return "";
        }
        if (K < 0 || idx == N) {
            return "0";
        }
      
        // Return the stored state
        if (dp[idx][K] != "-1")
            return dp[idx][K];
      
        // Including the digit (idx + 1)
        string include = (idx + 1).ToString() + recursion(arr, 0, N, K - arr[idx], dp);
      
        // Excluding the digit (idx + 1)
        string exclude = recursion(arr, idx + 1, N, K, dp);
      
        // Store the result and return
        return dp[idx][K] = getMaximum(include, exclude);
    }
      
    // Function to find the maximum number
    // formed such that the sum of the cost
    // digits in the formed number is K
    static string largestNumber(int[] arr, int N, int K)
    {
        // Stores all Dp-states
        List<List<string>> dp = new List<List<string>>();
        for(int i = 0; i < N + 1; i++)
        {
            dp.Add(new List<string>());
            for(int j = 0; j < K + 1; j++)
            {
                dp[i].Add("-1");
            }
        }
      
        // Recursive Call
        string ans = recursion(arr, 0, N, K, dp);
      
        // Return the result
        return (ans == "" ? "0" : ans);
    }
 
  static void Main() {
    int[] arr = {3, 12, 9, 5, 3, 4, 6, 5, 10};
    int K = 14;
    int N = arr.Length;
      
    Console.Write(largestNumber(arr, N, K));
  }
}
 
// This code is contributed by divyesh072019.

Javascript

<script>
// Javascript program for the above approach
 
// Function to find the maximum number
// among the two numbers S and T
function getMaximum(S, T)
{
 
  // If "0" exists in the string S
  if (S.indexOf("0") > -1) return T;
 
  // If "0" exists in the string T
  if (T.indexOf("0") > -1) return S;
 
  // Else return the maximum number
  // formed
  return S.length > T.length ? S : T;
}
 
// Recursive function to find maximum
// number formed such that the sum of
// cost of digits of formed number is K
function recursion(arr, idx, N, K, dp)
{
 
  // Base Case
  if (K == 0) {
    return "";
  }
  if (K < 0 || idx == N) {
    return "0";
  }
 
  // Return the stored state
  if (dp[idx][K] != "-1") return dp[idx][K];
 
  // Including the digit (idx + 1)
  let include = String(idx + 1) + recursion(arr, 0, N, K - arr[idx], dp);
 
  // Excluding the digit (idx + 1)
  let exclude = recursion(arr, idx + 1, N, K, dp);
 
  // Store the result and return
  return (dp[idx][K] = getMaximum(include, exclude));
}
 
// Function to find the maximum number
// formed such that the sum of the cost
// digits in the formed number is K
function largestNumber(arr, N, K)
{
 
  // Stores all Dp-states
  let dp = new Array(N + 1).fill(0).map(() => new Array(K + 1).fill(-1));
 
  // Recursive Call
  let ans = recursion(arr, 0, N, K, dp);
 
  // Return the result
  return ans == "" ? "0" : ans;
}
 
// Driver Code
let arr = [3, 12, 9, 5, 3, 4, 6, 5, 10];
let K = 14;
let N = arr.length;
 
document.write(largestNumber(arr, N, K));
 
// This code is contributed by _saurabh_jaiswal.
</script>
Producción: 

8555

 

Complejidad de Tiempo: O(9*K 2 )
Espacio Auxiliar: O(9*K)

Publicación traducida automáticamente

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