Dada una array arr[] de tamaño N que representa las denominaciones disponibles y un entero X . La tarea es encontrar cualquier combinación del número mínimo de monedas de las denominaciones disponibles tal que la suma de las monedas sea X. Si la suma dada no se puede obtener con las denominaciones disponibles, imprima -1 .
Ejemplos:
Entrada: X = 21, arr[] = {2, 3, 4, 5}
Salida: 2 4 5 5 5
Explicación:
una posible solución es {2, 4, 5, 5, 5} donde 2 + 4 + 5 + 5 + 5 = 21.
Otra posible solución es {3, 3, 5, 5, 5}.Entrada: X = 1, arr[] = {2, 4, 6, 9}
Salida: -1
Explicación:
Todas las monedas son mayores que 1. Por lo tanto, no existe solución.
Enfoque ingenuo: el enfoque más simple es probar todas las combinaciones posibles de denominaciones dadas de modo que en cada combinación, la suma de monedas sea igual a X. De estas combinaciones, elige la que tenga el mínimo número de monedas e imprímela. Si la suma de cualquier combinación no es igual a X , imprima -1 .
Complejidad temporal: O(X N )
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante la programación dinámica para encontrar la cantidad mínima de monedas . Al encontrar la cantidad mínima de monedas, se puede usar el retroceso para rastrear las monedas necesarias para que su suma sea igual a X . Siga los pasos a continuación para resolver el problema:
- Inicialice una array auxiliar dp[] , donde dp[i] almacenará la cantidad mínima de monedas necesarias para que la suma sea igual a i .
- Encuentre la cantidad mínima de monedas necesarias para que su suma sea igual a X usando el enfoque discutido en este artículo.
- Después de encontrar el número mínimo de monedas, use la técnica de retroceso para rastrear las monedas utilizadas, para que la suma sea igual a X.
- Al retroceder, recorra la array y elija una moneda que sea más pequeña que la suma actual, de modo que dp[sum_actual] sea igual a dp[sum_actual – moneda_elegida]+1 . Guarde la moneda elegida en una array.
- Después de completar el paso anterior, vuelva a retroceder pasando la suma actual como (suma actual – valor de moneda elegido) .
- Después de encontrar la solución, imprima la array de monedas elegidas.
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;
#define MAX 100000
// dp array to memoize the results
int dp[MAX + 1];
// List to store the result
list<int> denomination;
// Function to find the minimum number of
// coins to make the sum equals to X
int countMinCoins(int n, int C[], int m)
{
// Base case
if (n == 0) {
dp[0] = 0;
return 0;
}
// If previously computed
// subproblem occurred
if (dp[n] != -1)
return dp[n];
// Initialize result
int ret = INT_MAX;
// Try every coin that has smaller
// value than n
for (int i = 0; i < m; i++) {
if (C[i] <= n) {
int x
= countMinCoins(n - C[i],
C, m);
// Check for INT_MAX to avoid
// overflow and see if result
// can be minimized
if (x != INT_MAX)
ret = min(ret, 1 + x);
}
}
// Memoizing value of current state
dp[n] = ret;
return ret;
}
// Function to find the possible
// combination of coins to make
// the sum equal to X
void findSolution(int n, int C[], int m)
{
// Base Case
if (n == 0) {
// Print Solutions
for (auto it : denomination) {
cout << it << ' ';
}
return;
}
for (int i = 0; i < m; i++) {
// Try every coin that has
// value smaller than n
if (n - C[i] >= 0
and dp[n - C[i]] + 1
== dp[n]) {
// Add current denominations
denomination.push_back(C[i]);
// Backtrack
findSolution(n - C[i], C, m);
break;
}
}
}
// Function to find the minimum
// combinations of coins for value X
void countMinCoinsUtil(int X, int C[],
int N)
{
// Initialize dp with -1
memset(dp, -1, sizeof(dp));
// Min coins
int isPossible
= countMinCoins(X, C,
N);
// If no solution exists
if (isPossible == INT_MAX) {
cout << "-1";
}
// Backtrack to find the solution
else {
findSolution(X, C, N);
}
}
// Driver code
int main()
{
int X = 21;
// Set of possible denominations
int arr[] = { 2, 3, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
countMinCoinsUtil(X, arr, N);
return 0;
}
Java
// Java program for
// the above approach
import java.util.*;
class GFG{
static final int MAX = 100000;
// dp array to memoize the results
static int []dp = new int[MAX + 1];
// List to store the result
static List<Integer> denomination =
new LinkedList<Integer>();
// Function to find the minimum
// number of coins to make the
// sum equals to X
static int countMinCoins(int n,
int C[], int m)
{
// Base case
if (n == 0)
{
dp[0] = 0;
return 0;
}
// If previously computed
// subproblem occurred
if (dp[n] != -1)
return dp[n];
// Initialize result
int ret = Integer.MAX_VALUE;
// Try every coin that has smaller
// value than n
for (int i = 0; i < m; i++)
{
if (C[i] <= n)
{
int x = countMinCoins(n - C[i],
C, m);
// Check for Integer.MAX_VALUE to avoid
// overflow and see if result
// can be minimized
if (x != Integer.MAX_VALUE)
ret = Math.min(ret, 1 + x);
}
}
// Memoizing value of current state
dp[n] = ret;
return ret;
}
// Function to find the possible
// combination of coins to make
// the sum equal to X
static void findSolution(int n,
int C[], int m)
{
// Base Case
if (n == 0)
{
// Print Solutions
for (int it : denomination)
{
System.out.print(it + " ");
}
return;
}
for (int i = 0; i < m; i++)
{
// Try every coin that has
// value smaller than n
if (n - C[i] >= 0 &&
dp[n - C[i]] + 1 ==
dp[n])
{
// Add current denominations
denomination.add(C[i]);
// Backtrack
findSolution(n - C[i], C, m);
break;
}
}
}
// Function to find the minimum
// combinations of coins for value X
static void countMinCoinsUtil(int X,
int C[], int N)
{
// Initialize dp with -1
for (int i = 0; i < dp.length; i++)
dp[i] = -1;
// Min coins
int isPossible = countMinCoins(X, C, N);
// If no solution exists
if (isPossible == Integer.MAX_VALUE)
{
System.out.print("-1");
}
// Backtrack to find the solution
else
{
findSolution(X, C, N);
}
}
// Driver code
public static void main(String[] args)
{
int X = 21;
// Set of possible denominations
int arr[] = {2, 3, 4, 5};
int N = arr.length;
// Function Call
countMinCoinsUtil(X, arr, N);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above approach
import sys
MAX = 100000
# dp array to memoize the results
dp = [-1] * (MAX + 1)
# List to store the result
denomination = []
# Function to find the minimum number of
# coins to make the sum equals to X
def countMinCoins(n, C, m):
# Base case
if (n == 0):
dp[0] = 0
return 0
# If previously computed
# subproblem occurred
if (dp[n] != -1):
return dp[n]
# Initialize result
ret = sys.maxsize
# Try every coin that has smaller
# value than n
for i in range(m):
if (C[i] <= n):
x = countMinCoins(n - C[i], C, m)
# Check for INT_MAX to avoid
# overflow and see if result
#. an be minimized
if (x != sys.maxsize):
ret = min(ret, 1 + x)
# Memoizing value of current state
dp[n] = ret
return ret
# Function to find the possible
# combination of coins to make
# the sum equal to X
def findSolution(n, C, m):
# Base Case
if (n == 0):
# Print Solutions
for it in denomination:
print(it, end = " ")
return
for i in range(m):
# Try every coin that has
# value smaller than n
if (n - C[i] >= 0 and
dp[n - C[i]] + 1 == dp[n]):
# Add current denominations
denomination.append(C[i])
# Backtrack
findSolution(n - C[i], C, m)
break
# Function to find the minimum
# combinations of coins for value X
def countMinCoinsUtil(X, C,N):
# Initialize dp with -1
# memset(dp, -1, sizeof(dp))
# Min coins
isPossible = countMinCoins(X, C,N)
# If no solution exists
if (isPossible == sys.maxsize):
print("-1")
# Backtrack to find the solution
else:
findSolution(X, C, N)
# Driver code
if __name__ == '__main__':
X = 21
# Set of possible denominations
arr = [ 2, 3, 4, 5 ]
N = len(arr)
# Function call
countMinCoinsUtil(X, arr, N)
# This code is contributed by mohit kumar 29
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
static readonly int MAX = 100000;
// dp array to memoize the results
static int []dp = new int[MAX + 1];
// List to store the result
static List<int> denomination =
new List<int>();
// Function to find the minimum
// number of coins to make the
// sum equals to X
static int countMinCoins(int n,
int []C,
int m)
{
// Base case
if (n == 0)
{
dp[0] = 0;
return 0;
}
// If previously computed
// subproblem occurred
if (dp[n] != -1)
return dp[n];
// Initialize result
int ret = int.MaxValue;
// Try every coin that has smaller
// value than n
for (int i = 0; i < m; i++)
{
if (C[i] <= n)
{
int x = countMinCoins(n - C[i],
C, m);
// Check for int.MaxValue to avoid
// overflow and see if result
// can be minimized
if (x != int.MaxValue)
ret = Math.Min(ret, 1 + x);
}
}
// Memoizing value of current state
dp[n] = ret;
return ret;
}
// Function to find the possible
// combination of coins to make
// the sum equal to X
static void findSolution(int n,
int []C,
int m)
{
// Base Case
if (n == 0)
{
// Print Solutions
foreach (int it in denomination)
{
Console.Write(it + " ");
}
return;
}
for (int i = 0; i < m; i++)
{
// Try every coin that has
// value smaller than n
if (n - C[i] >= 0 &&
dp[n - C[i]] + 1 ==
dp[n])
{
// Add current denominations
denomination.Add(C[i]);
// Backtrack
findSolution(n - C[i], C, m);
break;
}
}
}
// Function to find the minimum
// combinations of coins for value X
static void countMinCoinsUtil(int X,
int []C,
int N)
{
// Initialize dp with -1
for (int i = 0; i < dp.Length; i++)
dp[i] = -1;
// Min coins
int isPossible = countMinCoins(X, C, N);
// If no solution exists
if (isPossible == int.MaxValue)
{
Console.Write("-1");
}
// Backtrack to find the solution
else
{
findSolution(X, C, N);
}
}
// Driver code
public static void Main(String[] args)
{
int X = 21;
// Set of possible denominations
int []arr = {2, 3, 4, 5};
int N = arr.Length;
// Function Call
countMinCoinsUtil(X, arr, N);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
var MAX = 100000;
// dp array to memoize the results
var dp = Array(MAX+1);
// List to store the result
var denomination = [];
// Function to find the minimum number of
// coins to make the sum equals to X
function countMinCoins(n, C, m)
{
// Base case
if (n == 0) {
dp[0] = 0;
return 0;
}
// If previously computed
// subproblem occurred
if (dp[n] != -1)
return dp[n];
// Initialize result
var ret = 1000000000;
// Try every coin that has smaller
// value than n
for (var i = 0; i < m; i++) {
if (C[i] <= n) {
var x
= countMinCoins(n - C[i],
C, m);
// Check for INT_MAX to avoid
// overflow and see if result
// can be minimized
if (x != 1000000000)
ret = Math.min(ret, 1 + x);
}
}
// Memoizing value of current state
dp[n] = ret;
return ret;
}
// Function to find the possible
// combination of coins to make
// the sum equal to X
function findSolution(n, C, m)
{
// Base Case
if (n == 0) {
denomination.forEach(it => {
document.write( it + ' ');
});
return;
}
for (var i = 0; i < m; i++) {
// Try every coin that has
// value smaller than n
if (n - C[i] >= 0
&& dp[n - C[i]] + 1
== dp[n]) {
// Add current denominations
denomination.push(C[i]);
// Backtrack
findSolution(n - C[i], C, m);
break;
}
}
}
// Function to find the minimum
// combinations of coins for value X
function countMinCoinsUtil(X, C, N)
{
// Initialize dp with -1
dp = Array(MAX+1).fill(-1);
// Min coins
var isPossible
= countMinCoins(X, C,
N);
// If no solution exists
if (isPossible == 1000000000) {
document.write( "-1");
}
// Backtrack to find the solution
else {
findSolution(X, C, N);
}
}
// Driver code
var X = 21;
// Set of possible denominations
var arr = [2, 3, 4, 5];
var N = arr.length;
// Function Call
countMinCoinsUtil(X, arr, N);
</script>
Producción:
2 4 5 5 5
Complejidad de tiempo: O(N*X), donde N es la longitud de la array dada y X es el número entero dado.
Espacio Auxiliar: O(N)