算法设计：找零钱问题介绍和详细解决方案|DP-7

2021年4月14日14:48:58 发表评论 679 次浏览

本文概述

给定一个值N, 如果我们要N分钱找零, 并且我们有无限数量的S = {S1, S2, .., Sm}硬币的供应, 我们可以用几种方法进行找零？硬币的顺序无关紧要。

例如, 对于N = 4和S = {1, 2, 3}, 有四个解：{1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}。因此输出应为4。对于N = 10且S = {2, 5, 3, 6}, 有五个解：{2, 2, 2, 2, 2}, {2, 2, 3, 3} {2, 2, 6}, {2, 3, 5}和{5, 5}。因此输出应为5。

1)最佳子结构

要计算解决方案的总数, 我们可以将所有解决方案分为两组。

1)不包含第m个硬币(或Sm)的解决方案。

2)包含至少1 Sm的溶液。

设count(S [], m, n)为计算解数的函数, 则可以写为count(S [], m-1, n)和count(S [], m, n-Sm)。

因此, 该问题具有最佳的子结构属性, 因为可以使用子问题的解决方案来解决该问题。

2)重叠子问题

以下是硬币更改问题的简单递归实现。该实现仅遵循上述递归结构。

C++

//Recursive C program for
//coin change problem.
#include<stdio.h>
  
//Returns the count of ways we can 
//sum S[0...m-1] coins to get sum n
int count( int S[], int m, int n )
{
     //If n is 0 then there is 1 solution 
     //(do not include any coin)
     if (n == 0)
         return 1;
      
     //If n is less than 0 then no 
     //solution exists
     if (n <0)
         return 0;
  
     //If there are no coins and n 
     //is greater than 0, then no
     //solution exist
     if (m <=0 && n>= 1)
         return 0;
  
     //count is sum of solutions (i) 
     //including S[m-1] (ii) excluding S[m-1]
     return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}
  
//Driver program to test above function
int main()
{
     int i, j;
     int arr[] = {1, 2, 3};
     int m = sizeof (arr)/sizeof (arr[0]);
     printf ( "%d " , count(arr, m, 4));
     getchar ();
     return 0;
}

Java

//Recursive java program for
//coin change problem.
import java.io.*;
  
class GFG {
      
     //Returns the count of ways we can 
     //sum S[0...m-1] coins to get sum n
     static int count( int S[], int m, int n )
     {
         //If n is 0 then there is 1 solution 
         //(do not include any coin)
         if (n == 0 )
             return 1 ;
          
         //If n is less than 0 then no 
         //solution exists
         if (n <0 )
             return 0 ;
      
         //If there are no coins and n 
         //is greater than 0, then no
         //solution exist
         if (m <= 0 && n>= 1 )
             return 0 ;
      
         //count is sum of solutions (i) 
         //including S[m-1] (ii) excluding S[m-1]
         return count( S, m - 1 , n ) +
                count( S, m, n-S[m- 1 ] );
     }
      
     //Driver program to test above function
     public static void main(String[] args)
     {
         int arr[] = { 1 , 2 , 3 };
         int m = arr.length;
         System.out.println( count(arr, m, 4 ));
          
          
     }
  
}
  
//This article is contributed by vt_m.

Python3

# Recursive Python3 program for
# coin change problem.
  
# Returns the count of ways we can sum
# S[0...m-1] coins to get sum n
def count(S, m, n ):
  
     # If n is 0 then there is 1
     # solution (do not include any coin)
     if (n = = 0 ):
         return 1
  
     # If n is less than 0 then no
     # solution exists
     if (n <0 ):
         return 0 ;
  
     # If there are no coins and n
     # is greater than 0, then no
     # solution exist
     if (m <= 0 and n> = 1 ):
         return 0
  
     # count is sum of solutions (i) 
     # including S[m-1] (ii) excluding S[m-1]
     return count( S, m - 1 , n ) + count( S, m, n - S[m - 1 ] );
  
# Driver program to test above function
arr = [ 1 , 2 , 3 ]
m = len (arr)
print (count(arr, m, 4 ))
  
# This code is contributed by Smitha Dinesh Semwal

C#

//Recursive C# program for
//coin change problem.
using System;
  
class GFG
{
     //Returns the count of ways we can 
     //sum S[0...m-1] coins to get sum n
     static int count( int []S, int m, int n )
     {
         //If n is 0 then there is 1 solution 
         //(do not include any coin)
         if (n == 0)
             return 1;
          
         //If n is less than 0 then no 
         //solution exists
         if (n <0)
             return 0;
      
         //If there are no coins and n 
         //is greater than 0, then no
         //solution exist
         if (m <=0 && n>= 1)
             return 0;
      
         //count is sum of solutions (i) 
         //including S[m-1] (ii) excluding S[m-1]
         return count( S, m - 1, n ) +
             count( S, m, n - S[m - 1] );
     }
      
     //Driver program
     public static void Main()
     {
          
         int []arr = {1, 2, 3};
         int m = arr.Length;
         Console.Write( count(arr, m, 4));
          
          
     }
}
//This code is contributed by Sam007

PHP

<?php
//Recursive PHP program for
//coin change problem.
  
//Returns the count of ways we can 
//sum S[0...m-1] coins to get sum n
function coun( $S , $m , $n )
{
      
     //If n is 0 then there is 
     //1 solution (do not include
     //any coin)
     if ( $n == 0)
         return 1;
      
     //If n is less than 0 then no 
     //solution exists
     if ( $n <0)
         return 0;
  
     //If there are no coins and n 
     //is greater than 0, then no
     //solution exist
     if ( $m <= 0 && $n>= 1)
         return 0;
  
     //count is sum of solutions (i) 
     //including S[m-1] (ii) excluding S[m-1]
     return coun( $S , $m - 1, $n ) + 
            coun( $S , $m , $n - $S [ $m - 1] );
}
  
     //Driver Code
     $arr = array (1, 2, 3);
     $m = count ( $arr );
     echo coun( $arr , $m , 4); 
      
//This code is contributed by Sam007
?>

输出：

4

应该注意的是, 上述函数一次又一次地计算相同的子问题。请参见以下递归树, 其中S = {1, 2, 3}, n = 5。

函数C({1}, 3)被调用两次。如果我们绘制完整的树, 则可以看到有许多子问题被多次调用。

C() --> count()
                             C({1, 2, 3}, 5)                     
                           /         \    
                         /             \                  
             C({1, 2, 3}, 2)                 C({1, 2}, 5)
            /   \                      /  \         
           /     \                    /     \   
C({1, 2, 3}, -1)  C({1, 2}, 2)        C({1, 2}, 3)    C({1}, 5)
               /\             / \           / \
             /   \           /   \         /    \
    C({1, 2}, 0)  C({1}, 2)   C({1, 2}, 1) C({1}, 3)    C({1}, 4)  C({}, 5)
                   /\     /\        /\         / \         
                  /\   /\     /\       /   \  
                .      .  .     .   .     .   C({1}, 3) C({}, 4)
                                               /\ 
                                              /\   
                                             .      .

由于再次调用了相同的问题, 因此此问题具有"重叠子问题"属性。因此, 硬币更改问题具有两个属性(请参见这个和这个)的动态编程问题。像其他典型的动态编程(DP)问题, 可以通过自下而上的方式构造一个临时数组table [] []来避免相同子问题的重新计算。

动态编程解决方案

C++

//C++ program for coin change problem.
#include<bits/stdc++.h>
  
using namespace std;
  
int count( int S[], int m, int n )
{
     int i, j, x, y;
  
     //We need n+1 rows as the table 
     //is constructed in bottom up
     //manner using the base case 0
     //value case (n = 0)
     int table[n + 1][m];
      
     //Fill the enteries for 0
     //value case (n = 0)
     for (i = 0; i <m; i++)
         table[0][i] = 1;
  
     //Fill rest of the table entries 
     //in bottom up manner 
     for (i = 1; i <n + 1; i++)
     {
         for (j = 0; j <m; j++)
         {
             //Count of solutions including S[j]
             x = (i-S[j]>= 0) ? table[i - S[j]][j] : 0;
  
             //Count of solutions excluding S[j]
             y = (j>= 1) ? table[i][j - 1] : 0;
  
             //total count
             table[i][j] = x + y;
         }
     }
     return table[n][m - 1];
}
  
//Driver Code
int main()
{
     int arr[] = {1, 2, 3};
     int m = sizeof (arr)/sizeof (arr[0]);
     int n = 4;
     cout <<count(arr, m, n);
     return 0;
}
  
//This code is contributed
//by Akanksha Rai(Abby_akku)

C

//C program for coin change problem.
#include<stdio.h>
  
int count( int S[], int m, int n )
{
     int i, j, x, y;
  
     //We need n+1 rows as the table is constructed 
     //in bottom up manner using the base case 0
     //value case (n = 0)
     int table[n+1][m];
     
     //Fill the enteries for 0 value case (n = 0)
     for (i=0; i<m; i++)
         table[0][i] = 1;
  
     //Fill rest of the table entries in bottom 
     //up manner  
     for (i = 1; i <n+1; i++)
     {
         for (j = 0; j <m; j++)
         {
             //Count of solutions including S[j]
             x = (i-S[j]>= 0)? table[i - S[j]][j]: 0;
  
             //Count of solutions excluding S[j]
             y = (j>= 1)? table[i][j-1]: 0;
  
             //total count
             table[i][j] = x + y;
         }
     }
     return table[n][m-1];
}
  
//Driver program to test above function
int main()
{
     int arr[] = {1, 2, 3};
     int m = sizeof (arr)/sizeof (arr[0]);
     int n = 4;
     printf ( " %d " , count(arr, m, n));
     return 0;
}

Java

/* Dynamic Programming Java implementation of Coin
    Change problem */
import java.util.Arrays;
  
class CoinChange
{
     static long countWays( int S[], int m, int n)
     {
         //Time complexity of this function: O(mn)
         //Space Complexity of this function: O(n)
  
         //table[i] will be storing the number of solutions
         //for value i. We need n+1 rows as the table is
         //constructed in bottom up manner using the base
         //case (n = 0)
         long [] table = new long [n+ 1 ];
  
         //Initialize all table values as 0
         Arrays.fill(table, 0 );   //O(n)
  
         //Base case (If given value is 0)
         table[ 0 ] = 1 ;
  
         //Pick all coins one by one and update the table[]
         //values after the index greater than or equal to
         //the value of the picked coin
         for ( int i= 0 ; i<m; i++)
             for ( int j=S[i]; j<=n; j++)
                 table[j] += table[j-S[i]];
  
         return table[n];
     }
  
     //Driver Function to test above function
     public static void main(String args[])
     {
         int arr[] = { 1 , 2 , 3 };
         int m = arr.length;
         int n = 4 ;
         System.out.println(countWays(arr, m, n));
     }
}
//This code is contributed by Pankaj Kumar

python

# Dynamic Programming Python implementation of Coin 
# Change problem
def count(S, m, n):
     # We need n+1 rows as the table is constructed 
     # in bottom up manner using the base case 0 value
     # case (n = 0)
     table = [[ 0 for x in range (m)] for x in range (n + 1 )]
  
     # Fill the entries for 0 value case (n = 0)
     for i in range (m):
         table[ 0 ][i] = 1
  
     # Fill rest of the table entries in bottom up manner
     for i in range ( 1 , n + 1 ):
         for j in range (m):
  
             # Count of solutions including S[j]
             x = table[i - S[j]][j] if i - S[j]> = 0 else 0
  
             # Count of solutions excluding S[j]
             y = table[i][j - 1 ] if j> = 1 else 0
  
             # total count
             table[i][j] = x + y
  
     return table[n][m - 1 ]
  
# Driver program to test above function
arr = [ 1 , 2 , 3 ]
m = len (arr)
n = 4
print (count(arr, m, n))
  
# This code is contributed by Bhavya Jain

C#

/* Dynamic Programming C# implementation of Coin
Change problem */
using System;
  
class GFG
{
     static long countWays( int []S, int m, int n)
     {
         //Time complexity of this function: O(mn)
         //Space Complexity of this function: O(n)
  
         //table[i] will be storing the number of solutions
         //for value i. We need n+1 rows as the table is
         //constructed in bottom up manner using the base
         //case (n = 0)
         int [] table = new int [n+1];
  
         //Initialize all table values as 0
         for ( int i = 0; i <table.Length; i++) 
         {
             table[i] = 0;
         }
  
         //Base case (If given value is 0)
         table[0] = 1;
  
         //Pick all coins one by one and update the table[]
         //values after the index greater than or equal to
         //the value of the picked coin
         for ( int i = 0; i <m; i++)
             for ( int j = S[i]; j <= n; j++)
                 table[j] += table[j - S[i]];
  
         return table[n];
     }
  
     //Driver Function
     public static void Main()
     {
         int []arr = {1, 2, 3};
         int m = arr.Length;
         int n = 4;
         Console.Write(countWays(arr, m, n));
     }
}
//This code is contributed by Sam007

PHP

<?php
//PHP program for 
//coin change problem.
  
function count1( $S , $m , $n )
{
     //We need n+1 rows as 
     //the table is constructed 
     //in bottom up manner 
     //using the base case 0
     //value case (n = 0)
     $table ;
     for ( $i = 0; $i <$n + 1; $i ++)
     for ( $j = 0; $j <$m ; $j ++)
         $table [ $i ][ $j ] = 0;
      
     //Fill the enteries for
     //0 value case (n = 0)
     for ( $i = 0; $i <$m ; $i ++)
         $table [0][ $i ] = 1;
  
     //Fill rest of the table 
     //entries in bottom up manner 
     for ( $i = 1; $i <$n + 1; $i ++)
     {
         for ( $j = 0; $j <$m ; $j ++)
         {
             //Count of solutions
             //including S[j]
             $x = ( $i - $S [ $j ]>= 0) ? 
                   $table [ $i - $S [ $j ]][ $j ] : 0;
  
             //Count of solutions
             //excluding S[j]
             $y = ( $j>= 1) ? 
                   $table [ $i ][ $j - 1] : 0;
  
             //total count
             $table [ $i ][ $j ] = $x + $y ;
         }
     }
     return $table [ $n ][ $m -1];
}
  
//Driver Code
$arr = array (1, 2, 3);
$m = count ( $arr );
$n = 4;
echo count1( $arr , $m , $n );
  
//This code is contributed by mits
?>

输出如下：

4

时间复杂度：O(百万)

以下是方法2的简化版本。此处所需的辅助空间仅为O(n)。

C/C++

int count( int S[], int m, int n )
{
     //table[i] will be storing the number of solutions for
     //value i. We need n+1 rows as the table is constructed
     //in bottom up manner using the base case (n = 0)
     int table[n+1];
  
     //Initialize all table values as 0
     memset (table, 0, sizeof (table));
  
     //Base case (If given value is 0)
     table[0] = 1;
  
     //Pick all coins one by one and update the table[] values
     //after the index greater than or equal to the value of the
     //picked coin
     for ( int i=0; i<m; i++)
         for ( int j=S[i]; j<=n; j++)
             table[j] += table[j-S[i]];
  
     return table[n];
}

Java

public static int count( int S[], int m, int n )
{
     //table[i] will be storing the number of solutions for
     //value i. We need n+1 rows as the table is constructed
     //in bottom up manner using the base case (n = 0)
     int table[]= new int [n+ 1 ];
  
     //Base case (If given value is 0)
     table[ 0 ] = 1 ;
  
     //Pick all coins one by one and update the table[] values
     //after the index greater than or equal to the value of the
     //picked coin
     for ( int i= 0 ; i<m; i++)
         for ( int j=S[i]; j<=n; j++)
             table[j] += table[j-S[i]];
  
     return table[n];
}

python

# Dynamic Programming Python implementation of Coin 
# Change problem
def count(S, m, n):
  
     # table[i] will be storing the number of solutions for
     # value i. We need n+1 rows as the table is constructed
     # in bottom up manner using the base case (n = 0)
     # Initialize all table values as 0
     table = [ 0 for k in range (n + 1 )]
  
     # Base case (If given value is 0)
     table[ 0 ] = 1
  
     # Pick all coins one by one and update the table[] values
     # after the index greater than or equal to the value of the
     # picked coin
     for i in range ( 0 , m):
         for j in range (S[i], n + 1 ):
             table[j] + = table[j - S[i]]
  
     return table[n]
  
# Driver program to test above function
arr = [ 1 , 2 , 3 ]
m = len (arr)
n = 4
x = count(arr, m, n)
print (x)
  
# This code is contributed by Afzal Ansari

C#

//Dynamic Programming C# implementation 
//of Coin Change problem
using System;
  
class GFG
{
static int count( int []S, int m, int n)
{
     //table[i] will be storing the 
     //number of solutions for value i.
     //We need n+1 rows as the table 
     //is constructed in bottom up manner
     //using the base case (n = 0)
     int [] table = new int [n + 1];
      
     //Base case (If given value is 0)
     table[0] = 1;
  
     //Pick all coins one by one and 
     //update the table[] values after 
     //the index greater than or equal 
     //to the value of the picked coin
     for ( int i = 0; i <m; i++)
         for ( int j = S[i]; j <= n; j++)
             table[j] += table[j - S[i]];
  
     return table[n];
}
  
//Driver Code
public static void Main()
{
     int []arr = {1, 2, 3};
     int m = arr.Length;
     int n = 4;
     Console.Write(count(arr, m, n));
}
}
  
//This code is contributed by Raj

PHP

<?php
function count_1( & $S , $m , $n )
{
     //table[i] will be storing the number 
     //of solutions for value i. We need n+1 
     //rows as the table is constructed in
     //bottom up manner using the base case (n = 0)
     $table = array_fill (0, $n + 1, NULl);
  
     //Base case (If given value is 0)
     $table [0] = 1;
  
     //Pick all coins one by one and update 
     //the table[] values after the index 
     //greater than or equal to the value 
     //of the picked coin
     for ( $i = 0; $i <$m ; $i ++)
         for ( $j = $S [ $i ]; $j <= $n ; $j ++)
             $table [ $j ] += $table [ $j - $S [ $i ]];
  
     return $table [ $n ];
}
  
//Driver Code
$arr = array (1, 2, 3);
$m = sizeof( $arr );
$n = 4;
$x = count_1( $arr , $m , $n );
echo $x ;
  
//This code is contributed
//by ChitraNayal
?>

输出如下：

4

感谢Rohan Laishram提出此空间优化版本的建议。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

参考文献：

http://www.algorithmist.com/index.php/Coin_Change

木子山

发表评论

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