如何更有效地計算組合數量？

Question

#include <stdio.h> 

void main() 
{ 
    int count = 0, amount, temp, n_200, n_100, n_50, n_20, n_10, n_5, n_2, n_1; /*count=check how much posibiliti you have,amount=the amount that the user enter ,n_200=bill of 200 nis ,n_100=bill of 100 nis.... n_1=1 nis coin.*/ 
    double min = 500, max = 0, current = 0;  
//part 2 of the job check the max and min whight... 

    while (1) {       //the progrem run all the time 
     printf_s("What is the amount that you like to check? (or press '0' to exit)\n"); 
     scanf_s("%d", &amount); 
     temp = amount; 
     if (amount == 0) 
//if the user click 0 the lop is finish and the progrem exit 
      return; 

     for (n_200 = 0; amount - n_200 >= 0; n_200 += 200)  
//first lop the duplicate of 200 
     { 

      for (n_100 = 0; amount - n_100 >= 0; n_100 += 100) 
//secend lop the duplicate of 100 
      { 


       for (n_50 = 0; amount - n_50 >= 0; n_50 += 50)  
//thired lop the duplicate of 50 
       { 


        for (n_20 = 0; (amount - n_20)/20 >= 0; n_20 += 20)  //fourth lop the duplicate of 20 
        { 


         for (n_10 = 0; amount - n_10 >= 0; n_10 += 10) 
//fifth lop the duplicate of 10 
         { 


          for (n_5 = 0; amount - n_5 >= 0; n_5 += 5)  
//six lop the duplicate of 5 
          { 


           for (n_2 = 0; amount - n_2 >= 0; n_2 += 2) //seventh lop the duplicate of 2 
           { 


            for (n_1 = 0; amount - n_1 >= 0; n_1 += 1) //eighth lop the duplicate of 1 
            { 
             temp = amount - n_200 - n_100 - n_50 - n_20 - n_10 - n_5 - n_2 - n_1; 


             if (temp == 0) { /////if temp==0 all the money is returend,the counter (posibiliti) is grow by one and the loop start again this time with other posibiliti. 
              count += 1; 

              current = current + (n_200/200 + n_100/100 + n_50/50 + n_20/20)*0.001 + (n_10/10)*0.007 + (n_5/5)*0.0082 + (n_2/2)*0.0057 + n_1*0.004; 
// In each variation we check the whight (curent) 
              if (current > max) 
//if the current is bigerr the max 
               max = current; 
//the progrem save it as max 
              if (current < min) 
//if the current is smaller the min 
               min = current; 
//the progrem save it as min`enter code here` 


              temp = amount; 
              current = 0; 
             } 
            } 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
     printf_s("\nThe number of possibilities is: %d.\n", count); 
     printf_s("The maximum weight is %.4lf [kg]\n", max); 
     printf_s("The minimmum weight is %.4lf [kg]\n\n", min); 
     count = 0;     //to start again we rest the deta the we get. 
     min = 500, max = 0, current = 0; 
    } 
} 

我需要計算總共有1,2,5,10,20,50,100,200加起來由用戶給定的數字有多少個組合。 例如，如果用戶輸入5，組合可以是：

1+1+1+1+1 
1+1+1+2 
2+2+1 
5 

Answer 1

蠻力：

#include <stdio.h> 

/* coin_types must be sorted from smallest to largest */ 
int count_coin_combinations(const unsigned *coin_types, unsigned num_coin_types, unsigned n) { 
    if (n == 0) 
     return 1; 

    int count = 0; 
    while (num_coin_types && *coin_types <= n) { 
     count += count_coin_combinations(coin_types, num_coin_types, n-*coin_types); 
     ++coin_types; 
     --num_coin_types; 
    } 

    return count; 
} 

int main() { 
    const unsigned coin_types[] = { 1, 2, 5, 10, 20, 50, 100, 200 }; 
    const unsigned num_coin_types = sizeof(coin_types)/sizeof(*coin_types); 

    unsigned n = 5; 
    unsigned count = count_coin_combinations(coin_types, num_coin_types, n); 
    printf("%d\n", count); 

    return 0; 
} 

輸出：

$ gcc -Wall -Wextra -pedantic -std=c99 -o a a.c && a 
4