title: Least number of stamps needed to pay certain postage
body: <p>I wrote a C program to solve the stamp and postage problem using brute force. However, it looks really stupid... Is there any better algorithms there to find the fewest number of stamps needed to pay certain postage?</p>
  <pre><code>const int denominations[] = {1, 5, 17, 23, 37, 50};
  int stamps[] = {0, 0, 0, 0, 0, 0};
  
  void ALG2(int p) { //p means postage
      int least = p;
      int i[] = {0, 0, 0, 0, 0, 0};
  
      for (i[0] = 0; i[0] &lt;= p / denominations[0]; i[0]++) { 
          for (i[1] = 0; i[1] &lt;= p / denominations[1]; i[1]++) {
              for (i[2] = 0; i[2] &lt;= p / denominations[2]; i[2]++) {
                  for (i[3] = 0; i[3] &lt;= p / denominations[3]; i[3]++) {
                      for (i[4] = 0; i[4] &lt;= p / denominations[4]; i[4]++) {
                          for (i[5] = 0; i[5] &lt;= p / denominations[5]; i[5]++) {
                              if (getSum(i) == p) {
                                  if (getCount(i) &lt; least) {
                                      least = getCount(i);
                                      for (int j = 0; j &lt; 6; j++)
                                          stamps[j] = i[j];
                                  }
                              }
                          }
                      }
                  }
              }
          }
      }
  }
  </code></pre>