Precio mínimo requerido para obtener N artículos de tipos dados

Dados los números enteros X , Y y Z , que representan los precios de 3 artículos A, B y C respectivamente, y dos números enteros a y b , que indican el recuento de dos tipos de artículos. La tarea es calcular el precio mínimo requerido para obtener N artículos del tipo A, B o C , donde A requiere 2 artículos del tipo a , B requiere 3 artículos del tipo b y C requiere 1 artículo del tipo a .y 1 artículo de tipo b .

Ejemplos:

Entrada: X = 300, Y = 200, Z = 100, N = 4, a = 3, b = 7
Salida: 500
Explicación: Se pueden formar cuatro artículos comprando 3 C (3*100 = 300) usando 3 a y 3 b y 1 B (1*200 = 200) usando 3 b. Precio final = 300 + 200 = 500, que es el mínimo posible.

Entrada: X=300, Y=150, Z=200, N=5, a=6, b=4
Salida: 1100

Enfoque: el problema anterior se puede resolver fijando el número de un artículo y verificando el precio requerido para formar los artículos restantes. Siga los pasos a continuación para resolver el problema:

• Inicialice la variable, diga minimal_bill para almacenar el precio mínimo requerido para comprar N artículos.
• Iterar sobre el rango C , menor o igual que N .
• Inicialice las variables, por ejemplo, maxorders_A es igual a (a – orders_C) / 2 y maxorders_B es igual a (b – orders_C) / 3.
• Compruebe si maxorders_A + maxorders_B + maxorders_C es menor que N , luego continúe.
• Si X es menor que Y , busque orders_A como min(maxorders_A, N – orders_C) y orders_B como N – orders_C – orders_A .
• De lo contrario, busque orders_B como min(maxorders_B, N – orders_C) y orders_A como N – orders_C – orders_B .
• Calcule la factura requerida en una variable, digamos factura, como (X * pedidos_A) + (Y * pedidos_B) + (Z * pedidos_C) .
• En cada iteración, actualice la factura_mínima como mínimo de factura_mínima y factura .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the minimum price
void FindBill(int X, int Y, int Z, int N,
              int a, int b)
{
 
    // Stores the amount required
    int minimum_bill = 10000000;
 
    // Iterating over total number
    // of possible items of type C
    for (int orders_C = 0; orders_C <= N; orders_C++) {
 
        // If count of a and b are less
        // than minimum required of type C
        if (a < orders_C or b < orders_C)
            break;
 
        // Maximum number of orders of type A
        int maxorders_A = (a - orders_C) / 2;
 
        // Maximum number of orders of type +B
        int maxorders_B = (b - orders_C) / 3;
 
        // Initializing the required
        // number of orders for A and B
        int orders_A = 0;
        int orders_B = 0;
 
        // Total items should be
        // greater than or equal to N
        if ((maxorders_A + maxorders_B + orders_C) < N) {
            continue;
        }
 
        // If cost of A < cost of B
        if (X < Y) {
 
            // Total orders of A will be minimum
            // of maximum orders of A or just
            // remaining orders required
            orders_A = min(maxorders_A, N - orders_C);
 
            // Remaining number of orders for B
            orders_B = N - orders_C - orders_A;
        }
 
        // If cost of A > cost of B
        else {
 
            // Total orders of B will be minimum
            // of maximum orders of B or just
            // remaining orders required
            orders_B = min(maxorders_B, N - orders_C);
 
            // Remaining number of orders for A
            orders_A = N - orders_C - orders_B;
        }
 
        // Calculating bill
        int bill = (X * orders_A)
                   + (Y * orders_B)
                   + (Z * orders_C);
 
        // Updating minimum_bill
        minimum_bill = min(bill, minimum_bill);
    }
 
    // If ordering N items is not possible
    if (minimum_bill == 10000000)
        minimum_bill = 0;
 
    // Printing minimum bill
    cout << minimum_bill << endl;
}
 
// Driver Code
int main()
{
 
    // Given Input
    int X = 300, Y = 150, Z = 200, N = 5, a = 6, b = 4;
 
    /// Function Call
    FindBill(X, Y, Z, N, a, b);
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG {
 
  // Function to calculate the minimum price
  static void FindBill(int X, int Y, int Z, int N,
                       int a, int b)
  {
 
    // Stores the amount required
    int minimum_bill = 10000000;
 
    // Iterating over total number
    // of possible items of type C
    for (int orders_C = 0; orders_C <= N; orders_C++) {
 
      // If count of a and b are less
      // than minimum required of type C
      if (a < orders_C || b < orders_C)
        break;
 
      // Maximum number of orders of type A
      int maxorders_A = (a - orders_C) / 2;
 
      // Maximum number of orders of type +B
      int maxorders_B = (b - orders_C) / 3;
 
      // Initializing the required
      // number of orders for A and B
      int orders_A = 0;
      int orders_B = 0;
 
      // Total items should be
      // greater than or equal to N
      if ((maxorders_A + maxorders_B + orders_C) < N) {
        continue;
      }
 
      // If cost of A < cost of B
      if (X < Y) {
 
        // Total orders of A will be minimum
        // of maximum orders of A or just
        // remaining orders required
        orders_A = Math.min(maxorders_A, N - orders_C);
 
        // Remaining number of orders for B
        orders_B = N - orders_C - orders_A;
      }
 
      // If cost of A > cost of B
      else {
 
        // Total orders of B will be minimum
        // of maximum orders of B or just
        // remaining orders required
        orders_B = Math.min(maxorders_B, N - orders_C);
 
        // Remaining number of orders for A
        orders_A = N - orders_C - orders_B;
      }
 
      // Calculating bill
      int bill = (X * orders_A)
        + (Y * orders_B)
        + (Z * orders_C);
 
      // Updating minimum_bill
      minimum_bill = Math.min(bill, minimum_bill);
    }
 
    // If ordering N items is not possible
    if (minimum_bill == 10000000)
      minimum_bill = 0;
 
    // Printing minimum bill
    System.out.println(minimum_bill);
  }
 
  // Driver Code
  public static void main (String[] args)
  {
 
    // Given Input
    int X = 300, Y = 150, Z = 200, N = 5, a = 6, b = 4;
 
    /// Function Call
    FindBill(X, Y, Z, N, a, b);
  }
}
 
// This code is contributed by Potta Lokesh

# Python program for the above approach
 
# Function to calculate the minimum price
def FindBill(X, Y, Z, N, a, b):
  # Stores the amount required
  minimum_bill = 10000000;
 
  # Iterating over total number
  # of possible items of type C
  for orders_C in range(0, N + 1):
     
    # If count of a and b are less
    # than minimum required of type C
    if (a < orders_C or b < orders_C): break;
 
    # Maximum number of orders of type A
    maxorders_A = (a - orders_C) // 2;
 
    # Maximum number of orders of type +B
    maxorders_B = (b - orders_C) // 3;
 
    # Initializing the required
    # number of orders for A and B
    orders_A = 0;
    orders_B = 0;
 
    # Total items should be
    # greater than or equal to N
    if (maxorders_A + maxorders_B + orders_C < N):
      continue;
 
 
    # If cost of A < cost of B
    if (X < Y):
      # Total orders of A will be minimum
      # of maximum orders of A or just
      # remaining orders required
      orders_A = min(maxorders_A, N - orders_C);
 
      # Remaining number of orders for B
      orders_B = N - orders_C - orders_A;
     
 
    # If cost of A > cost of B
    else:
      # Total orders of B will be minimum
      # of maximum orders of B or just
      # remaining orders required
      orders_B = min(maxorders_B, N - orders_C);
 
      # Remaining number of orders for A
      orders_A = N - orders_C - orders_B;
     
 
    # Calculating bill
    bill = X * orders_A + Y * orders_B + Z * orders_C;
 
    # Updating minimum_bill
    minimum_bill = min(bill, minimum_bill);
   
 
  # If ordering N items is not possible
  if (minimum_bill == 10000000): minimum_bill = 0;
 
  # Printing minimum bill
  print(minimum_bill);
 
 
# Driver Code
 
# Given Input
X = 300
Y = 150
Z = 200
N = 5
a = 6
b = 4
 
#/ Function Call
FindBill(X, Y, Z, N, a, b);
 
# This code is contributed by gfgking.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to calculate the minimum price
static void FindBill(int X, int Y, int Z, int N,
              int a, int b)
{
 
    // Stores the amount required
    int minimum_bill = 10000000;
 
    // Iterating over total number
    // of possible items of type C
    for (int orders_C = 0; orders_C <= N; orders_C++) {
 
        // If count of a and b are less
        // than minimum required of type C
        if (a < orders_C || b < orders_C)
            break;
 
        // Maximum number of orders of type A
        int maxorders_A = (a - orders_C) / 2;
 
        // Maximum number of orders of type +B
        int maxorders_B = (b - orders_C) / 3;
 
        // Initializing the required
        // number of orders for A and B
        int orders_A = 0;
        int orders_B = 0;
 
        // Total items should be
        // greater than or equal to N
        if ((maxorders_A + maxorders_B + orders_C) < N) {
            continue;
        }
 
        // If cost of A < cost of B
        if (X < Y) {
 
            // Total orders of A will be minimum
            // of maximum orders of A or just
            // remaining orders required
            orders_A = Math.Min(maxorders_A, N - orders_C);
 
            // Remaining number of orders for B
            orders_B = N - orders_C - orders_A;
        }
 
        // If cost of A > cost of B
        else {
 
            // Total orders of B will be minimum
            // of maximum orders of B or just
            // remaining orders required
            orders_B = Math.Min(maxorders_B, N - orders_C);
 
            // Remaining number of orders for A
            orders_A = N - orders_C - orders_B;
        }
 
        // Calculating bill
        int bill = (X * orders_A)
                   + (Y * orders_B)
                   + (Z * orders_C);
 
        // Updating minimum_bill
        minimum_bill = Math.Min(bill, minimum_bill);
    }
 
    // If ordering N items is not possible
    if (minimum_bill == 10000000)
        minimum_bill = 0;
 
    // Printing minimum bill
    Console.Write(minimum_bill);
}
 
// Driver Code
public static void Main()
{
 
    // Given Input
    int X = 300, Y = 150, Z = 200, N = 5, a = 6, b = 4;
 
    /// Function Call
    FindBill(X, Y, Z, N, a, b);
}
}
 
// This code is contributed by ipg2016107.

<script>
// Javascript program for the above approach
 
// Function to calculate the minimum price
function FindBill(X, Y, Z, N, a, b) {
  // Stores the amount required
  let minimum_bill = 10000000;
 
  // Iterating over total number
  // of possible items of type C
  for (let orders_C = 0; orders_C <= N; orders_C++) {
    // If count of a and b are less
    // than minimum required of type C
    if (a < orders_C || b < orders_C) break;
 
    // Maximum number of orders of type A
    let maxorders_A = Math.floor((a - orders_C) / 2);
 
    // Maximum number of orders of type +B
    let maxorders_B = (b - orders_C) / 3;
 
    // Initializing the required
    // number of orders for A and B
    let orders_A = 0;
    let orders_B = 0;
 
    // Total items should be
    // greater than or equal to N
    if (maxorders_A + maxorders_B + orders_C < N) {
      continue;
    }
 
    // If cost of A < cost of B
    if (X < Y) {
      // Total orders of A will be minimum
      // of maximum orders of A or just
      // remaining orders required
      orders_A = Math.min(maxorders_A, N - orders_C);
 
      // Remaining number of orders for B
      orders_B = N - orders_C - orders_A;
    }
 
    // If cost of A > cost of B
    else {
      // Total orders of B will be minimum
      // of maximum orders of B or just
      // remaining orders required
      orders_B = Math.min(maxorders_B, N - orders_C);
 
      // Remaining number of orders for A
      orders_A = N - orders_C - orders_B;
    }
 
    // Calculating bill
    let bill = X * orders_A + Y * orders_B + Z * orders_C;
 
    // Updating minimum_bill
    minimum_bill = Math.min(bill, minimum_bill);
  }
 
  // If ordering N items is not possible
  if (minimum_bill == 10000000) minimum_bill = 0;
 
  // Printing minimum bill
  document.write(minimum_bill);
}
 
// Driver Code
 
// Given Input
let X = 300,
  Y = 150,
  Z = 200,
  N = 5,
  a = 6,
  b = 4;
 
/// Function Call
FindBill(X, Y, Z, N, a, b);
 
// This code is contributed by gfgking.
</script>

1100

Complejidad temporal: O(N)
Espacio auxiliar: O(1)