permutations based problem

Hi,
I was given a problem at school...it is...

Making Change
You are given a limited number of coins of various denominations, and a certain amount. You are to compuate how many ways there are 2 pick the coins to add up 2 that amount. For e.g., given 12 coins of 1-cent value, 2 coins of 5-cent value and 3 coins of 10-cent value, and an amount of 15 cents, there are 4 combinations:

- 2 5-cent coins and 5 1-cent coins
- 1 5-cent coins and 10 1-cent coins
- 1 10-cent coin and 1 5-cent coins
- 1 10-cent coin and 5 1-cent coins

The answer (output) should therefore be 4.

The input will b read from a text file.

first line of input file = no. of different coin denominations.
second line = total amount to b made up

The remaining lines of the input file each consist of a pair of +ve integers representing a coin denomination followed by the no. of coins of the denomination avail. All nos. r in the range [1,100]

SAMPLE INPUT
3
15
1 12
5 2
10 3

SAMPLE OUTPUT
4

Here's an approach to problems that I recommend--attempt to answer the question, or set up the algorhythm to solve the probelm, using pencil and paper before writing the code. Doing so often allows you to write the code much easier.

For this problem I would start by listing the universe of coins that might appear in the file. In US coinage that would be pennies, nickels, dimes, quarters, fifty cent pieces and silverdollars.

According to the requirements of the problem I will be given a file with a set of information indicating how many of each of those coins I will be given and what the target amount is. The task is to figure out how many ways it can be done with the coins given.

Therefore, I will need some place to store the number of each coin available, some place to store the goal, and some place to store the number of successful combinations I've found.

To find each combination I will first start assuming I have no coins of any denomination. Each coin represents an integer value that can be added up like this 0*1 + 0*5 + 0*10 + 0*25 + 0*50 + 0*100 for total of 0. I compare that total to the goal and if it is the same increment the number of successful comibinations. I repeat the process until I have tried all other combinations. To do this in an orderly fashion, say I still "pretend" I have no coins except a penny the next time through, then only two pennies the time after that, up to however many pennies I am given, but no other coins. Then I "pretend" I have only one nickel and no pennies, then 1N and 1P, then 1N and 2P, etc until I have looked at all possibilities allowed. This serial approach suggests a group of nested control loops, each loop representing the number of coins of that denomination that time through the loop. There may or may not be coins of a given denomination in a given run of the loop, or in a given scenario presented in the file.

Now how to get the data out of the file. Use of streams or file pointers is the way to do this in C++. Since all data appears to be separated/delimited from each other by a space or a new line char then use of the extraction operator should suffice. Reading in each piece of data in the sequence provided by the assignment instructions allows me to fill the various variables with data. With the algorhythm above all coins will be used, although some may be zero every time through the loop. The initial value in the file meaningful in that it tells you how long that scenario in the file is. The second value is goal amount for that scenario. Now there is the information regarding the various coins for the given scenario. Using a loop looping the initial value of the scenario number of times I can extract the int representing which each coin present in this scenario and the number of that type of coin I have available to use in that scenario. I would probably use a switch statement whose conditional is the coin's integer value. In each case statement I would read the value of the number of coins for this scenario into the appropriate variable.

when all the loops have been run looking at all the combinations I can write the value of the number of successful combinations to the screen or a file or wherever I need to send it.

Then I can go on to the next scenario in the file, if there is another one.

Now I need to convert this to code, but the algorhythm almost does it for me.

Learning how to set up such algorhythms is an important part of learning how to become a programmer, but it is a separate art from learning how to program with a given language. If you don't like setting up the algorhytms, you are probably not going to like writing programs either.

Thank you 4 the reply guest.

But, the problem is that the denominations are variable - e.g. they can even give me

3 coins of 4-cent value or 5 coins or 34-cent value... which are of course not available practically ...

which means that there's something more involved then the algorithm you just gave ... because ur algo. just assumes a fixed possible denominations available which is not the case.

although i think i can proceed a bit further through you algorithm...

thanx again 4 replying....
anyway

:(

:rolleyes: Hey,
I've finally solved this problem. I must say that "guest"'s idea + some of my modifications really did it, good. I don't think any more faster or efficient algo. is possible for it....

THANK YOU guest

SOURCE CODE

#include <stdio.h>
#include <conio.H>
#include <stdlib.h>
#include <iostream.h>

struct coin {
int no;
int denomination;
int currentvalue;
} *coins;

void main()
{
clrscr();
int n,total;
char tmp[100];
FILE *fp = fopen("currency.inp","r");
fgets(&tmp[0],100,fp);
n = atoi(tmp);
fgets(&tmp[0],100,fp);
total = atoi(tmp);
coins = new coin [n];
for (int i=0;i!=n;i++) {
fgets(&tmp[0],100,fp);
sscanf(tmp,"%d %d",&coins[i].denomination,&coins[i].no);
coins[i].currentvalue = 0;
}
int value=0;
int answer=0;
while (1) {
value=0;
for (i=0;i!=n;i++) {
value += (coins[i].currentvalue * coins[i].denomination);
}
if (value==total) {
answer++;
}
coins[0].currentvalue++;
for (i=0;i!=n-1;i++) {
if (coins[i].currentvalue > coins[i].no) {
coins[i].currentvalue = 0;
coins[i+1].currentvalue++;
}
}

if (coins[n-1].currentvalue > coins[n-1].no) {
break;
}
}
printf("\n%d",answer);
delete [] coins;
}

currency.inp - sample input file
3
15
1 12
5 2
10 3