본문 바로가기

Programming/Project Euler

[C/C++] Project Euler #31 - Coin Sums

In the UK, the following coin denominations are available:
• 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p).

The goal is to find the number of unique combinations of these coins that sum to 200 pence (£2).

Conditions:
1. Coins can be used repeatedly as needed.
2. The order of coins does not matter (e.g., {1p, 2p} is considered the same as {2p, 1p}).
3. Only unique combinations should be counted.


 

In this problem, a recursive function was created to solve the task.

For instance, to calculate how to sum up to 200 pence, we start with the largest coin denomination and decide how many of that coin to use. For the remaining amount, the next smallest coin is used to determine the number of combinations.

Let the coin denominations be represented as  \(coins_1\)  to  \(coins_8\), corresponding to 200p, 100p, 50p, 20p, 10p, 5p, 2p, and 1p, respectively. Then, the number of combinations  \(Comb(n, i)\), which represents the number of ways to form a total of  n  pence using coins of denomination  i  or smaller, can be expressed recursively as:


\[Comb(n, i) = \sum_{k=0}^{\lfloor n / coins_i \rfloor} Comb(n - k \cdot coins_i, i + 1)\]


Here:
•  k  is the number of coins of denomination  i  used.
•  \(Comb(n - k \cdot coins_i, i + 1)\)  calculates the remaining combinations using the next smaller denomination.

 

coin sums


This recursive approach can be implemented programmatically. The following is the source code for this logic (provided for reference only).

//------------------------------------------------
//    Project Euler #31 - Coin Sums
//        - by Aubrey Choi
//        - created at 2015-02-04
//------------------------------------------------
#include <stdio.h>

int getcomb(int n, int d);

int main()
{
    printf("Ans = %d\n", getcomb(200, 0));
}

int getcomb(int n, int d)
{
    const int v[] = { 200, 100, 50, 20, 10, 5, 2, 1, 0 };

    if( n == 0 ) return 1;
    if( v[d] == 0 ) return 0;

    int sum = 0;
    int t = n/v[d];
    for( int i = 0 ; i <= t ; i++ )
        sum += getcomb(n-i*v[d], d+1);
    return sum;
}