Suppose we have eight different denominations of coins {1,2,5,10,20,50,100,200} and combine these coins to form a given number n. For example, if n=200, one possible combination is 200 = 3 * 1 + 1 * 2 + 1 * 5 + 2 * 20 + 1 * 50 + 1 * 100. How many possible combinations are there?

Given a sum, suppose we have m coins of different types {V1, V2… Vm}, if we want to combine sum, then we have

Sum = x1 * V1 + x2 * V2 +… + xm * Vm

To find all possible combinations is to find the coefficients that satisfy the preceding equivalence {x1, x2… All the possible numbers of xm}.

X1 = {0, 1… , sum/V1}, x2 = {0, 1… , sum/ V2} and so on. O (sum/V1 * sum/V2 * sum/V3 *…)

(2) The sum of m coins is the sum of m coins. The sum of m coins is the sum of m coins. (3) The sum of m coins is the sum of m coins. , sum/Vm}, in other words, the combination of the equations in the above analysis and the following equations is equivalent.

Sum = x1 * V1 + x2 * V2 +… + 0 * Vm

Sum = x1 * V1 + x2 * V2 +… + 1 * Vm

Sum = x1 * V1 + x2 * V2 +… + 2 * Vm

…

Sum = x1 * V1 + x2 * V2 +… + K * Vm

Where K is the maximum value that xm can take K = sum/Vm. But what good was it? Don’t worry, let’s define the following variables first:

Dp [I][sum] = all combinations of the previous I coins to form sum.

Dp [m][sum] = dp[m][sum] = dp[m] In the union equation above: how many combinations are there when xn=0? In fact, the sum of the former i-1 coin is dp[i-1][sum]. When xn is equal to 1, how many combinations are there? It is actually the number of combinations of the former i-1 coins (sum -Vm), including dp[I -1][sum -Vm]; Xn =2, dp[I -1][sum – 2 Vm], etc. All of these cases add up to our dp[I][sum]. So:

dp[i][sum] = dp[i-1][sum – 0Vm] + dp[i-1][sum – 1Vm]

Dp [i-1][sum – 2Vm] +… + dp[i-1][sum – KVm]; K = sum/Vm, or a more abstract mathematical description:

The recursive formula

By using this formula, we can see that the problem has been reduced step by step, so what is the initial case? If sum is equal to 0, then no matter how many ways there are to combine 0, there’s only one way that the coefficients are equal to 0;

Dp [I][0] = 1 // I = 0, 1, 2… , m

If we represent dp[I][sum] as a two-digit array, we find that the values of row I depend entirely on the values of row i-1, so we can evaluate the array row by row. If the sum of the first 0 coins is to be made, we specify dp[0][sum] = 0.

If N is small, the value of each coin can be N/coins at most. Note that N >200 is required in this program; otherwise, the position of if judgment needs to be changed. (Time out)

#include<stdio.h> void brute(int coins[],int n,int cb){// For (int I =0; i<=n/coins[0]; i++){ for(int j =0; j<=n/coins[1]; j++){ for(int k =0; k<=n/coins[2]; k++){ for(int l =0; l<=n/coins[3]; l++){ for(int m =0; m<=n/coins[4]; m++){ for(int o =0; o<=n/coins[5]; o++){ for(int p =0; p<=n/coins[6]; p++){ if((coins[0]*i+coins[1]*j+coins[2]*k+coins[3]*l+coins[4]*m+coins[5]*o+coins[6]*p)==n){ cb++; Printf ("1 2 5 10 20 50 100 use %d %d %d %d %d %d %d %d \n", I,j,k,l,m,o,p); }; } } } } } } } } int main() { int cb=0,num; scanf("%d",&num); Int COINS [7] =,2,5,10,20,50,100 {1}; brute(coins,num,cb); }Copy the code

Note that each coin is allowed to be used multiple times, and 122 is in the same case as 212 and 221. Therefore, limit the currency used each time (Coins [I]) to be greater than or equal to the currency used last time (Coins [coinlocation]) (time out).

static int cc = 0; Static int[] sum = {0,0,0,0,0,0}; /** * @param Coins list * @param n total amount * @param count Current amount * @param coinLocation Current currency subscript */ public static void dfs(int[] coins,int n,int count,int coinlocation){ if(count==n){ cc++; for(int i =0; i<sum.length; I++) {System. Out. Print (" use "+ COINS + + sum" yuan: "[I] [I] +", "); } System.out.println(); }else if(count > n){ return; }else {// iterate over each coin, allow 1,2,2, disallow 2, 1,2 for(int I =coinlocation; i<coins.length; i++){ sum[i]++; dfs(coins,n,count+coins[i],i); sum[i]--; }}}Copy the code

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Dynamic programming sets d[I][sum] as the number of schemes to reach the sum of the total amount when using the coin in I. Therefore, for coins I (COINS [I]), there is no need to use I, one I, two I… Sum /coins[I] = 1; d[0] =0; d[0][I] =0

public static void dynamic_prommgram(int[] coins,int n){ int[][] d = new int[coins.length+1][n+1]; //length+1 does not apply to any currency, only 1, only 1 2, only 1 2 3...... N +1 = 0, 1..... For (int I = 0; i<=coins.length; i++) d[i][0] = 1; for(int i = 1 ; i<=coins.length; Int sum = 1; int sum = 1; int sum = 1; sum<=n; Sum++){// because d[I][0]==1, so j from 1 for(int k=0; k<=sum/coins[i-1]; K++) {/ /, for example, the use value to 1, the corresponding COINS is [] the subscript I - 1, the logic of upriver in fact is not consistent with the d [I] [sum] [I - 1) + = d [sum - k * COINS [I - 1]]. } } } System.out.println(d[coins.length][n]); }Copy the code

Of course, the program can be simplified to a one-dimensional array. The two-dimensional array is easy to understand, but the one-dimensional array is more concise, because D [I][sum]=ξ’d [I -2][X ‘]=ξ’d [I -2][X ‘]=… D [i-1] is the intermediate quantity of the summation, so it can be directly expressed as a one-dimensional array:

long[] d= new long[201]; d[0]=1; Int [] v =,2,5,10,20,50,100 {1}; for(int i=0; i<7; i++){ for(int j=v[i]; j<201; j++){ d[j]+=d[j-v[i]]; / / equivalent to}} System. Out. Println (200 + "combinations" + d [200] + ""); }Copy the code