生成总和等于给定值的最小硬币组合 _数据结构

本文概述

C ++
Java
Python3
C#

arr[]数组的大小为N代表可用的教派和整数x的任务是找到任何结合可用的最小数量的硬币面额,硬币的总和是x,如果给定的总和不能得到可用的教派,打印1。
例子：

输入：X = 21, arr [] = {2, 3, 4, 5}
输出：2 4 5 5 5
说明：一种可能的解决方案是{2, 4, 5, 5, 5}, 其中2 + 4 + 5 + 5 + 5 =21。另一个可能的解决方案是{3, 3, 5, 5, 5}。
输入：X = 1, arr [] = {2, 4, 6, 9}
输出：-1
说明：所有硬币都大于1。因此, 不存在解。

简单的方法:最简单的方法是尝试给定面额的所有可能的组合，在每个组合中，硬币的总和等于x。从这些组合中，选择一个有最少硬币数量的并打印它。如果任意组合的和不等于X，则输出-1。
时间复杂度：O(X^N)
辅助空间：O(N)
有效方法:上述方法可以通过动态规划进行优化，找到最小硬币数量。在找到最小硬币数量的同时，回溯可以用来追踪使其总和等于x所需的硬币，按照以下步骤解决问题:

初始化辅助数组dp [], 在哪里dp [i]将存储求和所需的最小硬币数量等于一世.
找到使它们的总和等于的最小硬币数量X使用中讨论的方法这个文章。
找到最小数量的硬币后, 使用回溯技术追踪使用的硬币, 使总和等于X.
在回溯中遍历数组并选择一个比当前总和还小的硬币dp [current_sum]等于dp [current_sum – selected_coin] +1。将所选硬币存储在阵列中。
完成上述步骤后, 通过传递当前金额as(当前金额–选择的硬币价值).
找到解决方案后, 打印选定硬币的阵列。

下面是上述方法的实现：
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# 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

输出如下：