Encuentra el número mínimo de monedas que hacen un valor dado

 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *