Se le da una lista de N monedas de diferentes denominaciones. Puede pagar una cantidad equivalente a cualquier moneda 1 y puede adquirir esa moneda. Además, una vez que hayamos pagado una moneda, podremos elegir como máximo K monedas más y podremos adquirirlas gratis. La tarea es encontrar la cantidad mínima requerida para adquirir todas las N monedas por un valor dado de K.
Ejemplos:
Input : coin[] = {100, 20, 50, 10, 2, 5},
k = 3
Output : 7
Input : coin[] = {1, 2, 5, 10, 20, 50},
k = 3
Output : 3
Según la pregunta, podemos ver que a un costo de 1 moneda, podemos adquirir como máximo K+1 monedas. Por tanto, para adquirir todas las n monedas, estaremos eligiendo ceil(n/(k+1)) monedas y el coste de elegir monedas será mínimo si elegimos el ceil(n/(k+1)) más pequeño. (Aproximación codiciosa). Las monedas ceil(n/(k+1)) más pequeñas se pueden encontrar simplemente ordenando todos los valores N en orden creciente.
Si debemos verificar la complejidad del tiempo (n log n) es para clasificar el elemento y (k) es para agregar la cantidad total. Entonces, finalmente Complejidad de Tiempo: O(n log n).
C++
// C++ program to acquire all n coins
#include<bits/stdc++.h>
using namespace std;
// function to calculate min cost
int minCost(int coin[], int n, int k)
{
// sort the coins value
sort(coin, coin + n);
// calculate no. of
// coins needed
int coins_needed = ceil(1.0 * n /
(k + 1));
// calculate sum of
// all selected coins
int ans = 0;
for (int i = 0; i <= coins_needed - 1;
i++)
ans += coin[i];
return ans;
}
// Driver Code
int main()
{
int coin[] = {8, 5, 3, 10,
2, 1, 15, 25};
int n = sizeof(coin) / sizeof(coin[0]);
int k = 3;
cout << minCost(coin, n, k);
return 0;
}
Java
// Java program to acquire
// all n coins
import java.util.Arrays;
class GFG
{
// function to calculate min cost
static int minCost(int coin[],
int n, int k)
{
// sort the coins value
Arrays.sort(coin);
// calculate no. of
// coins needed
int coins_needed = (int)Math.ceil(1.0 *
n / (k + 1));
// calculate sum of
// all selected coins
int ans = 0;
for (int i = 0; i <= coins_needed - 1;
i++)
ans += coin[i];
return ans;
}
// Driver code
public static void main(String arg[])
{
int coin[] = { 8, 5, 3, 10,
2, 1, 15, 25 };
int n = coin.length;
int k = 3;
System.out.print(minCost(coin, n, k));
}
}
// This code is contributed
// by Anant Agarwal.
Python3
# Python3 program to # acquire all n coins import math # function to calculate min cost def minCost(coin, n, k): # sort the coins value coin.sort() # calculate no. of # coins needed coins_needed = math.ceil(1.0 * n // (k + 1)); # calculate sum of all # selected coins ans = 0 for i in range(coins_needed - 1 + 1): ans += coin[i] return ans # Driver code coin = [8, 5, 3, 10, 2, 1, 15, 25] n = len(coin) k = 3 print(minCost(coin, n, k)) # This code is contributed # by Anant Agarwal.
C#
// C# program to acquire all n coins
using System;
class GFG
{
// function to calculate min cost
static int minCost(int []coin,
int n, int k)
{
// sort the coins value
Array.Sort(coin);
// calculate no. of coins needed
int coins_needed = (int)Math.Ceiling(1.0 *
n / (k + 1));
// calculate sum of
// all selected coins
int ans = 0;
for (int i = 0; i <= coins_needed - 1; i++)
ans += coin[i];
return ans;
}
// Driver code
public static void Main()
{
int []coin = {8, 5, 3, 10,
2, 1, 15, 25};
int n = coin.Length;
int k = 3;
// Function calling
Console.Write(minCost(coin, n, k));
}
}
// This code is contributed
// by nitin mittal.
PHP
<?php
// PHP program to acquire all n coins
// function to calculate min cost
function minCost($coin, $n, $k)
{
// sort the coins value
sort($coin); sort($coin,$n);
// calculate no. of coins needed
$coins_needed = ceil(1.0 * $n / ($k + 1));
// calculate sum of
// all selected coins
$ans = 0;
for ($i = 0; $i <= $coins_needed - 1; $i++)
$ans += $coin[$i];
return $ans;
}
// Driver Code
{
$coin = array(8, 5, 3, 10,
2, 1, 15, 25);
$n = sizeof($coin) / sizeof($coin[0]);
$k = 3;
echo minCost($coin, $n, $k);
return 0;
}
// This code is contributed
// by nitin mittal.
?>
Javascript
<script>
// Javascript program to acquire all n coins
// Function to calculate min cost
function minCost(coin, n, k)
{
// Sort the coins value
coin.sort(function(a, b){return a - b})
// Calculate no. of
// coins needed
var coins_needed = Math.ceil(n /(k + 1));
// Calculate sum of
// all selected coins
var ans = 0;
for(var i = 0; i <= coins_needed - 1; i++)
ans += coin[i];
return ans;
}
// Driver Code
var coin = [ 8, 5, 3, 10,
2, 1, 15, 25 ]
var n = coin.length;
var k = 3;
document.write(minCost(coin, n, k));
// This code is contributed by noob2000
</script>
Producción :
3
Complejidad de tiempo: O(n log n)
Espacio auxiliar: O(1)
Tenga en cuenta que existen enfoques más eficientes para encontrar el número dado de valores más pequeños. Por ejemplo, el método 6 de m elementos más grandes (o más pequeños) en una array puede encontrar el m-ésimo elemento más pequeño en (nm) Log m + m Log m).
¿Cómo manejar múltiples consultas para una sola array predefinida?
En este caso, si se le pide que encuentre la respuesta anterior para muchos valores de K, debe calcularla rápidamente y nuestra complejidad de tiempo aumentó según la cantidad de consultas para k. Con el propósito de servir, podemos mantener una array de suma de prefijos después de ordenar todos los valores N y podemos responder consultas de manera fácil y rápida.
Suponer
C++
// C++ program to acquire all
// n coins at minimum cost
// with multiple values of k.
#include<bits/stdc++.h>
using namespace std;
// Converts coin[] to prefix sum array
void preprocess(int coin[], int n)
{
// sort the coins value
sort(coin, coin + n);
// Maintain prefix sum array
for (int i = 1; i <= n - 1; i++)
coin[i] += coin[i - 1];
}
// Function to calculate min
// cost when we can get k extra
// coins after paying cost of one.
int minCost(int coin[], int n, int k)
{
// calculate no. of coins needed
int coins_needed = ceil(1.0 * n / (k + 1));
// return sum of from prefix array
return coin[coins_needed - 1];
}
// Driver Code
int main()
{
int coin[] = {8, 5, 3, 10,
2, 1, 15, 25};
int n = sizeof(coin) / sizeof(coin[0]);
preprocess(coin, n);
int k = 3;
cout << minCost(coin, n, k) << endl;
k = 7;
cout << minCost(coin, n, k) << endl;
return 0;
}
Java
// C# program to acquire all n coins at
// minimum cost with multiple values of k.
import java .io.*;
import java.util.Arrays;
public class GFG {
// Converts coin[] to prefix sum array
static void preprocess(int []coin, int n)
{
// sort the coins value
Arrays.sort(coin);
// Maintain prefix sum array
for (int i = 1; i <= n - 1; i++)
coin[i] += coin[i - 1];
}
// Function to calculate min cost when we
// can get k extra coins after paying
// cost of one.
static int minCost(int []coin, int n, int k)
{
// calculate no. of coins needed
int coins_needed =(int) Math.ceil(1.0
* n / (k + 1));
// return sum of from prefix array
return coin[coins_needed - 1];
}
// Driver Code
static public void main (String[] args)
{
int []coin = {8, 5, 3, 10, 2, 1, 15, 25};
int n = coin.length;
preprocess(coin, n);
int k = 3;
System.out.println(minCost(coin, n, k));
k = 7;
System.out.println( minCost(coin, n, k));
}
}
// This code is contributed by anuj_67.
Python3
# Python3 program to acquire all n coins at # minimum cost with multiple values of k. import math as mt # Converts coin[] to prefix sum array def preprocess(coin, n): # sort the coins values coin.sort() # maintain prefix sum array for i in range(1, n): coin[i] += coin[i - 1] # Function to calculate min cost when we can # get k extra coins after paying cost of one. def minCost(coin, n, k): # calculate no. of coins needed coins_needed = mt.ceil(1.0 * n / (k + 1)) # return sum of from prefix array return coin[coins_needed - 1] # Driver code coin = [8, 5, 3, 10, 2, 1, 15, 25] n = len(coin) preprocess(coin, n) k = 3 print(minCost(coin, n, k)) k = 7 print(minCost(coin, n, k)) # This code is contributed # by Mohit kumar 29
C#
// C# program to acquire all n coins at
// minimum cost with multiple values of k.
using System;
public class GFG {
// Converts coin[] to prefix sum array
static void preprocess(int []coin, int n)
{
// sort the coins value
Array.Sort(coin);
// Maintain prefix sum array
for (int i = 1; i <= n - 1; i++)
coin[i] += coin[i - 1];
}
// Function to calculate min cost when we
// can get k extra coins after paying
// cost of one.
static int minCost(int []coin, int n, int k)
{
// calculate no. of coins needed
int coins_needed =(int) Math.Ceiling(1.0
* n / (k + 1));
// return sum of from prefix array
return coin[coins_needed - 1];
}
// Driver Code
static public void Main ()
{
int []coin = {8, 5, 3, 10, 2, 1, 15, 25};
int n = coin.Length;
preprocess(coin, n);
int k = 3;
Console.WriteLine(minCost(coin, n, k));
k = 7;
Console.WriteLine( minCost(coin, n, k));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to acquire all n coins at
// minimum cost with multiple values of k.
// Converts coin[] to prefix sum array
function preprocess(&$coin, $n)
{
// sort the coins value
sort($coin);
// Maintain prefix sum array
for ($i = 1; $i <= $n - 1; $i++)
$coin[$i] += $coin[$i - 1];
}
// Function to calculate min cost
// when we can get k extra coins
// after paying cost of one.
function minCost(&$coin, $n, $k)
{
// calculate no. of coins needed
$coins_needed = ceil(1.0 * $n / ($k + 1));
// return sum of from prefix array
return $coin[$coins_needed - 1];
}
// Driver Code
$coin = array(8, 5, 3, 10,
2, 1, 15, 25);
$n = sizeof($coin);
preprocess($coin, $n);
$k = 3;
echo minCost($coin, $n, $k) . "\n";
$k = 7;
echo minCost($coin, $n, $k) . "\n";
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript program to acquire all n coins at
// minimum cost with multiple values of k.
// Converts coin[] to prefix sum array
function preprocess(coin,n)
{
// sort the coins value
coin.sort(function(a,b){return a-b;});
// Maintain prefix sum array
for (let i = 1; i <= n - 1; i++)
coin[i] += coin[i - 1];
}
// Function to calculate min cost when we
// can get k extra coins after paying
// cost of one.
function minCost(coin,n,k)
{
// calculate no. of coins needed
let coins_needed =Math.ceil(1.0
* n / (k + 1));
// return sum of from prefix array
return coin[coins_needed - 1];
}
// Driver Code
let coin=[8, 5, 3, 10, 2, 1, 15, 25];
let n = coin.length;
preprocess(coin, n);
let k = 3;
document.write(minCost(coin, n, k)+"<br>");
k = 7;
document.write( minCost(coin, n, k));
// This code is contributed by rag2127
</script>
Producción :
3 1
Complejidad de tiempo: O(n log n)
Espacio auxiliar: O(1)
Después del preprocesamiento, cada consulta de ak toma un tiempo O(1).
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA