UOJ Money : Dynamic Programming

Each country’s banknotes come in different denominations. In Malaysia, the denominations for the banknotes are 1, 5, 10, 20, 50, and 100.

Your task is to find the number of unique combinations of banknotes to get a given amount of money.

Input

  • The first line of the input contains an integer N, the amount of money.
  • The second line of the input contains an integer D, the number of denominations.
  • The next D lines each contain an integer representing the face value of one of the denominations. You may assume that each of these D integers are unique.

OUTPUT

Output the total number of ways to obtain N dollars.

CONSTRAINTS

  • Time Limit: 3s
  • Memory Limit: 64MB
  • N and D are chosen such that N * D is at most 100,000.

Problem Source: UTP Online Judge

This problem can’t even be solved by the elementary for algorithm. However, Dynamic Programming (DP) still works effectively. Before I present my solution, I want to explain a slightly less used piece of code:

(a < b ? p : q)

This means that if a is less than b, take the result of p, else q. Of course, you can still use the typical if...else algorithm, but if you are familiar with this, it will make your code looks simpler and may come in handy sometimes. Now, we can construct our code:

#include <iostream>;

using namespace std;

int main() {

	int N, D;
	cin << N << D;

	int table[N+1][D];
	int money[D];

	for (int i=0; i<D; i++){
		cin << money[i];
	}
	
	for (int i=0; i<=N; i++){
		for (int j=0; j<D; j++){
			if (i==0 || j==0) table[i][j] = 1;
			else table[i][j] = 0;
		}
	}

	for (int i=1; i<=N; i++){
		for (int j=1; j<D; j++){
			table[i][j] = table[i][j-1] + 
            ( i < money[j] ? 0 : table[i - money[j]][j]);
		}
	}

	cout << table[N][D-1];

	return 0;
}

The code works as follow: First, we construct a table with N+1 rows (an additional row is added for the 0-th) and D columns. table[i][j] is the number of combinations to obtain i money with using j+1 banknotes. For example, table[5][1] is the number of combinations to obtain money in RM 5 with the first 2 type of banknotes. After we finish filling up the table, we can just call table[N][D-1] as our output.

So, how should we fill up our table? We fill every element in the 0-th row and 0-th column with 1. This is because there is only one combination to obtain RM 0: No banknote at all. Next, for every amount of money, there is also only one combination to obtain that amount of money using the first banknote: No banknote at all or use all that banknote to achieve that value. This is done by the code:

for (int i=0; i<=N; i++){
	for (int j=0; j<D; j++){
		if (i==0 || j==0) table[i][j] = 1;
		else table[i][j] = 0;
	}
}

For other elements, the number of combination must be larger than the element at its left, which is the number of combination to achieve the money with one banknote less. The additional combination is the tricky part. If the money is lower than the additional banknote, no additional combination is added. Else, add the combination of the difference of the money and the additional banknote. This part is complete in the code:

for (int i=1; i<=N; i++){
	for (int j=1; j<D; j++){
		table[i][j] = table[i][j-1] + 
            ( i < money[j] ? 0 : table[i - money[j]][j]);
	}
}
Advertisements
UOJ Money : Dynamic Programming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s