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

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

## 本文概述

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

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]) {

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 =

//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])
{

//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]):

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])
{

//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