Least number of stamps needed to pay certain postage [closed]

Question

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?

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] <= p / denominations[0]; i[0]++) { 
        for (i[1] = 0; i[1] <= p / denominations[1]; i[1]++) {
            for (i[2] = 0; i[2] <= p / denominations[2]; i[2]++) {
                for (i[3] = 0; i[3] <= p / denominations[3]; i[3]++) {
                    for (i[4] = 0; i[4] <= p / denominations[4]; i[4]++) {
                        for (i[5] = 0; i[5] <= p / denominations[5]; i[5]++) {
                            if (getSum(i) == p) {
                                if (getCount(i) < least) {
                                    least = getCount(i);
                                    for (int j = 0; j < 6; j++)
                                        stamps[j] = i[j];
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

Answer 1

Is there any better algorithms there to find the fewest number of stamps needed to pay certain postage?

Some ideas:

1. Rather than for (i[n] = 0; i[n] <= p / denominations[n]; i[n]++) {, only need to loop to for (i[n] = 0; i[n] <= (p - current_sum)/ denominations[n]; i[n]++) {

2. Loop first with largest denomination stamps first.

3. Quit the loops if the exact sum found.