生成总和等于给定值的最小硬币组合

2021年4月26日16:24:46 发表评论 931 次浏览

本文概述

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所需的硬币，按照以下步骤解决问题:

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

下面是上述方法的实现：

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

输出如下：

2 4 5 5 5

时间复杂度：O(N * X), 其中N是给定数组的长度, X是给定整数。

辅助空间：O(N)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: