Wie berechnet man die Anzahl der Kombinationen effizienter?

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; 
    } 
} 

Ich muss berechnen, wie viele Kombinationen gibt es für die Summe von 1, 2, 5, 10, 20, 50, 100, 200 bis zu einer bestimmten Anzahl durch den Benutzer. Zum Beispiel, wenn der Benutzer 5 eintritt, können die Kombinationen sein:

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

Answer 1

Brute-Force:

#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; 
} 

Ausgang:

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