Dado un valor V , si queremos hacer un cambio de V centavos, y tenemos una oferta infinita de cada una de las monedas valoradas en C = { C1, C2, .., Cm} , ¿cuál es el número mínimo de monedas para hacer el cambio? ¿cambio? Si no es posible realizar un cambio, imprima -1 .
Ejemplos:
C++
// A Naive recursive C++ program to find minimum of coins
// to make a given change V
#include<bits/stdc++.h>
using namespace std;
// m is size of coins array (number of different coins)
int minCoins(int coins[], int m, int V)
{
// base case
if (V == 0) return 0;
// Initialize result
int res = INT_MAX;
// Try every coin that has smaller value than V
for (int i=0; i<m; i++)
{
if (coins[i] <= V)
{
int sub_res = minCoins(coins, m, V-coins[i]);
// Check for INT_MAX to avoid overflow and see if
// result can minimized
if (sub_res != INT_MAX && sub_res + 1 < res)
res = sub_res + 1;
}
}
return res;
}
// Driver program to test above function
int main()
{
int coins[] = {9, 6, 5, 1};
int m = sizeof(coins)/sizeof(coins[0]);
int V = 11;
cout << "Minimum coins required is "
<< minCoins(coins, m, V);
return 0;
}
Java
// A Naive recursive JAVA program to find minimum of coins
// to make a given change V
class coin
{
// m is size of coins array (number of different coins)
static int minCoins(int coins[], int m, int V)
{
// base case
if (V == 0) return 0;
// Initialize result
int res = Integer.MAX_VALUE;
// Try every coin that has smaller value than V
for (int i=0; i<m; i++)
{
if (coins[i] <= V)
{
int sub_res = minCoins(coins, m, V-coins[i]);
// Check for INT_MAX to avoid overflow and see if
// result can minimized
if (sub_res != Integer.MAX_VALUE && sub_res + 1 < res)
res = sub_res + 1;
}
}
return res;
}
public static void main(String args[])
{
int coins[] = {9, 6, 5, 1};
int m = coins.length;
int V = 11;
System.out.println("Minimum coins required is "+ minCoins(coins, m, V) );
}
}/* This code is contributed by Rajat Mishra */
Python3
# A Naive recursive python program to find minimum of coins
# to make a given change V
import sys
# m is size of coins array (number of different coins)
def minCoins(coins, m, V):
# base case
if (V == 0):
return 0
# Initialize result
res = sys.maxsize
# Try every coin that has smaller value than V
for i in range(0, m):
if (coins[i] <= V):
sub_res = minCoins(coins, m, V-coins[i])
# Check for INT_MAX to avoid overflow and see if
# result can minimized
if (sub_res != sys.maxsize and sub_res + 1 < res):
res = sub_res + 1
return res
# Driver program to test above function
coins = [9, 6, 5, 1]
m = len(coins)
V = 11
print("Minimum coins required is",minCoins(coins, m, V))
# This code is contributed by
# Smitha Dinesh Semwal
C#
// A Naive recursive C# program
// to find minimum of coins
// to make a given change V
using System;
class coin
{
// m is size of coins array
// (number of different coins)
static int minCoins(int []coins, int m, int V)
{
// base case
if (V == 0) return 0;
// Initialize result
int res = int.MaxValue;
// Try every coin that has
// smaller value than V
for (int i = 0; i < m; i++)
{
if (coins[i] <= V)
{
int sub_res = minCoins(coins, m,
V - coins[i]);
// Check for INT_MAX to
// avoid overflow and see
// if result can minimized
if (sub_res != int.MaxValue &&
sub_res + 1 < res)
res = sub_res + 1;
}
}
return res;
}
// Driver Code
public static void Main()
{
int []coins = {9, 6, 5, 1};
int m = coins.Length;
int V = 11;
Console.Write("Minimum coins required is "+
minCoins(coins, m, V));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// A Naive recursive PHP
// program to find minimum
// of coins to make a given
// change V
// m is size of coins array
// (number of different coins)
function minCoins($coins,
$m, $V)
{
// base case
if ($V == 0) return 0;
// Initialize result
$res = PHP_INT_MAX;
// Try every coin that has
// smaller value than V
for ($i = 0; $i < $m; $i++)
{
if ($coins[$i] <= $V)
{
$sub_res = minCoins($coins, $m,
$V - $coins[$i]);
// Check for INT_MAX to
// avoid overflow and see
// if result can minimized
if ($sub_res != PHP_INT_MAX &&
$sub_res + 1 < $res)
$res = $sub_res + 1;
}
}
return $res;
}
// Driver Code
$coins = array(9, 6, 5, 1);
$m = sizeof($coins);
$V = 11;
echo "Minimum coins required is ",
minCoins($coins, $m, $V);
// This code is contributed by ajit
?>
Javascript
<script>
// A Naive recursive Javascript program to
// find minimum of coins to make a given
// change V
// m is size of coins array
// (number of different coins)
function minCoins(coins, m, V)
{
// Base case
if (V == 0)
return 0;
// Initialize result
let res = Number.MAX_VALUE;
// Try every coin that has smaller
// value than V
for(let i = 0; i < m; i++)
{
if (coins[i] <= V)
{
let sub_res = minCoins(coins, m,
V - coins[i]);
// Check for INT_MAX to avoid overflow and
// see if result can minimized
if (sub_res != Number.MAX_VALUE &&
sub_res + 1 < res)
res = sub_res + 1;
}
}
return res;
}
// Driver code
let coins = [ 9, 6, 5, 1 ];
let m = coins.length;
let V = 11;
document.write("Minimum coins required is " +
minCoins(coins, m, V) );
// This code is contributed by avanitrachhadiya2155
</script>
C++
// A Dynamic Programming based C++ program to find minimum of coins
// to make a given change V
#include<bits/stdc++.h>
using namespace std;
// m is size of coins array (number of different coins)
int minCoins(int coins[], int m, int V)
{
// table[i] will be storing the minimum number of coins
// required for i value. So table[V] will have result
int table[V+1];
// Base case (If given value V is 0)
table[0] = 0;
// Initialize all table values as Infinite
for (int i=1; i<=V; i++)
table[i] = INT_MAX;
// Compute minimum coins required for all
// values from 1 to V
for (int i=1; i<=V; i++)
{
// Go through all coins smaller than i
for (int j=0; j<m; j++)
if (coins[j] <= i)
{
int sub_res = table[i-coins[j]];
if (sub_res != INT_MAX && sub_res + 1 < table[i])
table[i] = sub_res + 1;
}
}
if(table[V]==INT_MAX)
return -1;
return table[V];
}
// Driver program to test above function
int main()
{
int coins[] = {9, 6, 5, 1};
int m = sizeof(coins)/sizeof(coins[0]);
int V = 11;
cout << "Minimum coins required is "
<< minCoins(coins, m, V);
return 0;
}
Java
// A Dynamic Programming based Java
// program to find minimum of coins
// to make a given change V
import java.io.*;
class GFG
{
// m is size of coins array
// (number of different coins)
static int minCoins(int coins[], int m, int V)
{
// table[i] will be storing
// the minimum number of coins
// required for i value. So
// table[V] will have result
int table[] = new int[V + 1];
// Base case (If given value V is 0)
table[0] = 0;
// Initialize all table values as Infinite
for (int i = 1; i <= V; i++)
table[i] = Integer.MAX_VALUE;
// Compute minimum coins required for all
// values from 1 to V
for (int i = 1; i <= V; i++)
{
// Go through all coins smaller than i
for (int j = 0; j < m; j++)
if (coins[j] <= i)
{
int sub_res = table[i - coins[j]];
if (sub_res != Integer.MAX_VALUE
&& sub_res + 1 < table[i])
table[i] = sub_res + 1;
}
}
if(table[V]==Integer.MAX_VALUE)
return -1;
return table[V];
}
// Driver program
public static void main (String[] args)
{
int coins[] = {9, 6, 5, 1};
int m = coins.length;
int V = 11;
System.out.println ( "Minimum coins required is "
+ minCoins(coins, m, V));
}
}
//This Code is contributed by vt_m.
Python3
# A Dynamic Programming based Python3 program to
# find minimum of coins to make a given change V
import sys
# m is size of coins array (number of
# different coins)
def minCoins(coins, m, V):
# table[i] will be storing the minimum
# number of coins required for i value.
# So table[V] will have result
table = [0 for i in range(V + 1)]
# Base case (If given value V is 0)
table[0] = 0
# Initialize all table values as Infinite
for i in range(1, V + 1):
table[i] = sys.maxsize
# Compute minimum coins required
# for all values from 1 to V
for i in range(1, V + 1):
# Go through all coins smaller than i
for j in range(m):
if (coins[j] <= i):
sub_res = table[i - coins[j]]
if (sub_res != sys.maxsize and
sub_res + 1 < table[i]):
table[i] = sub_res + 1
if table[V] == sys.maxsize:
return -1
return table[V]
# Driver Code
if __name__ == "__main__":
coins = [9, 6, 5, 1]
m = len(coins)
V = 11
print("Minimum coins required is ",
minCoins(coins, m, V))
# This code is contributed by ita_c
C#
// A Dynamic Programming based
// Java program to find minimum
// of coins to make a given
// change V
using System;
class GFG
{
// m is size of coins array
// (number of different coins)
static int minCoins(int []coins,
int m, int V)
{
// table[i] will be storing
// the minimum number of coins
// required for i value. So
// table[V] will have result
int []table = new int[V + 1];
// Base case (If given
// value V is 0)
table[0] = 0;
// Initialize all table
// values as Infinite
for (int i = 1; i <= V; i++)
table[i] = int.MaxValue;
// Compute minimum coins
// required for all
// values from 1 to V
for (int i = 1; i <= V; i++)
{
// Go through all coins
// smaller than i
for (int j = 0; j < m; j++)
if (coins[j] <= i)
{
int sub_res = table[i - coins[j]];
if (sub_res != int.MaxValue &&
sub_res + 1 < table[i])
table[i] = sub_res + 1;
}
}
return table[V];
}
// Driver Code
static public void Main ()
{
int []coins = {9, 6, 5, 1};
int m = coins.Length;
int V = 11;
Console.WriteLine("Minimum coins required is " +
minCoins(coins, m, V));
}
}
// This code is contributed
// by akt_mit
PHP
<?php
// A Dynamic Programming based
// PHP program to find minimum
// of coins to make a given
// change V.
// m is size of coins
// array (number of different coins)
function minCoins($coins, $m, $V)
{
// table[i] will be storing the
// minimum number of coins
// required for i value. So
// table[V] will have result
$table[$V + 1] = array();
// Base case (If given
// value V is 0)
$table[0] = 0;
// Initialize all table
// values as Infinite
for ($i = 1; $i <= $V; $i++)
$table[$i] = PHP_INT_MAX;
// Compute minimum coins
// required for all
// values from 1 to V
for ($i = 1; $i <= $V; $i++)
{
// Go through all coins
// smaller than i
for ($j = 0; $j < $m; $j++)
if ($coins[$j] <= $i)
{
$sub_res = $table[$i - $coins[$j]];
if ($sub_res != PHP_INT_MAX &&
$sub_res + 1 < $table[$i])
$table[$i] = $sub_res + 1;
}
}
if ($table[$V] == PHP_INT_MAX)
return -1;
return $table[$V];
}
// Driver Code
$coins = array(9, 6, 5, 1);
$m = sizeof($coins);
$V = 11;
echo "Minimum coins required is ",
minCoins($coins, $m, $V);
// This code is contributed by ajit
?>
Javascript
<script>
// A Dynamic Programming based Javascript
// program to find minimum of coins
// to make a given change V
// m is size of coins array
// (number of different coins)
function minCoins(coins,m,v)
{
// table[i] will be storing
// the minimum number of coins
// required for i value. So
// table[V] will have result
let table = new Array(V+1);
// Initialize first table value as zero
table[0] = 0;
// Initialize all table values as Infinite except for the first one
for (let i = 1; i <= V; i++)
{
table[i] = Number.MAX_VALUE;
}
// Compute minimum coins required for all
// values from 1 to V
for (let i = 1; i <= V; i++)
{
// Go through all coins smaller than i
for (let j = 0; j < m; j++)
if (coins[j] <= i)
{
let sub_res = table[i - coins[j]];
if (sub_res != Number.MAX_VALUE
&& sub_res + 1 < table[i])
table[i] = sub_res + 1;
}
}
if(table[V] == Number.MAX_VALUE)
return -1;
return table[V];
}
// Driver program
let coins = [9, 6, 5, 1];
let m = coins.length;
let V = 11;
document.write( "Minimum coins required is " + minCoins(coins, m, V))
// This code is contributed by rag2127
</script>
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