给定一个值V，如果我们想对V美分进行更改，并且我们有无限量的C={C1，C2，…，Cm}值硬币，那么进行更改的最小硬币数量是多少？如果无法进行更改，请打印-1。
null
例如：
Input: coins[] = {25, 10, 5}, V = 30Output: Minimum 2 coins requiredWe can use one coin of 25 cents and one of 5 cents Input: coins[] = {9, 6, 5, 1}, V = 11Output: Minimum 2 coins requiredWe can use one coin of 6 cents and 1 coin of 5 cents
这个问题是所讨论问题的变体 硬币兑换问题 在这里，我们不需要找到可能的解决方案的总数，而是需要找到硬币数量最少的解决方案。
可以使用下面的递归公式计算V值的最小硬币数。
If V == 0, then 0 coins required.If V > 0 minCoins(coins[0..m-1], V) = min {1 + minCoins(V-coin[i])} where i varies from 0 to m-1 and coin[i] <= V
下面是基于上述递归公式的递归解决方案。
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> |
输出：
Minimum coins required is 2
上述解的时间复杂度是指数的。如果我们画出完整的递归树，我们可以观察到许多子问题一次又一次地被解决。例如，当我们从V=11开始，我们可以通过减去1 5次，再减去5一次，得到6。所以6的子问题被称为两次。
由于再次调用相同的子问题，此问题具有重叠子问题属性。所以min coins问题有两个属性（参见 这 和 这 )一个动态规划问题。像其他典型的 动态规划问题 ，可以通过以自下而上的方式构造临时数组表[]，避免重新计算相同的子问题。下面是基于动态规划的解决方案。
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); for (let i = 0; i < V + 1; i++) { table[i] = 0; } // Initialize all table values as Infinite 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> |
输出：
Minimum coins required is 2
上述解的时间复杂度为O（mV）。
感谢小悟空在评论中提出上述解决方案 在这里 感谢Vignesh Mohan提出这个问题和初步解决方案。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
