[Ricendithas]

Hi! This is the code I am using:

import java.util.*;
import java.io.*;

public class CountingChange {
	
	public static int[] coin = {50, 25, 10, 5, 1};
	public static long[] nway = new long[10000];
	
	public static void main(String[] args) throws FileNotFoundException {
		Scanner iFile = new Scanner(System.in);
		int amount = iFile.nextInt();
		
		nway[0] = 1;
		for(int i = 0; i < coin.length; i++) {
			int c = coin[i];
			for(int j = c; j <= amount; j++)
				nway[j] += nway[j-c]; // THIS ONE. WHAT'S THE USE OF THIS?
		}
		
		for(int i = 0; i <= amount; i++)
			System.out.print(nway[i] + " ");
		
		System.out.println();
		System.out.println(nway[amount]);
	}
}

So, I was wondering, what does the one with the comment do? I mean, what's the purpose of having that?

Thanks.

[mostyfriedman]

it adds the element at index j in array nway to the element at nway[j-c]; and assigns the result back to nway[j]

[Ricendithas]

mostyfriedman, on 5 Oct, 2009 - 05:17 AM, said:

it adds the element at index j in array nway to the element at nway[j-c]; and assigns the result back to nway[j]

What I mean is that what is the main purpose of having it there? And why must we add it to the element at nway[j-c]?

[mostyfriedman]

sorry but i can't answer that since i don't know what the algorithm is supposed to be doing

[NeoTifa]

Yea, it subtracts the current element of the coin array from the current nway element. That code doesn't make a lot of since. Where is it from and what is it SUPPOSED to do?

[LaFayette]

My deductive skill tells me that it's an algorithm that count the number of ways you can create change for a certain amount.

suppose we know the number of ways nway[A] to make change for amout A with coins c1, c2,...,c{k-1}, and for all amounts less then A (with cons c1,..., ck). The number of ways to make change for A including coin ck is then equal to nway[A] + the number of ways to do it for amount A-ck (with ck included);

nway[A] += nway[A-ck]

Perhaps not entirely obvious that this works though, but it does!

This post has been edited by LaFayette: 05 October 2009 - 12:17 PM

[pbl]

One thing for sure, without this statement the nway[] array will never be initialized
Looks like a very complicated way to figure out how many coins of each type should be given to provide the change for a certain amount using an iteration rather than a simple divide followed my a modulo to find the change still to be reimburse

[LaFayette]

Quote

Looks like a very complicated way to figure out how many coins of each type should be given to provide ..

It doesnt figure that out. It figures out how many combinations of the given coins there exists that adds up to the amount given.

[pbl]

LaFayette, on 6 Oct, 2009 - 02:20 AM, said:

Quote

Looks like a very complicated way to figure out how many coins of each type should be given to provide ..

It doesnt figure that out. It figures out how many combinations of the given coins there exists that adds up to the amount given.

That makes more sense