/* Optimal coin set computation by brute force, 2 coin variant */
/* Compile with e.g.:
    gcc -O3 CoinBruteForce_2c.c -o CoinBruteForce_2c
 * or:
    icc -O3 CoinBruteForce_2c.c -o CoinBruteForce_2c
    
 * Run as:
    ./CoinBruteForce_2c
 *   
 
   * Created by Sebastiaan Breedveld *
   http://sebastiaanbreedveld.nl/
 *
 * License: The Unlicense (http://unlicense.org/): do with it whatever you want.
 *
 */

#include <limits.h>
#include <stdio.h>

/* Maximum change is 499 cents */
/* Trick! If you change this to 99 cents, you are able to compute systems which start with 5 cents (and are multiple of 5 cents) */
#define MaxAmount 499

/* Define number of coins in this system */
#define NrCoins 2

/* uint32 should be sufficient and not too limiting */
typedef unsigned int INTTYPE;
#define INTMAX UINT_MAX;

INTTYPE MakeChangeProblem(const INTTYPE Total, const INTTYPE *CoinSet); 

int main(void)
{ 
    /* Inits */
    INTTYPE CoinSet[NrCoins] = {1, 2};
    INTTYPE TotalCoins, c1, MinAmount = INTMAX;
      
    for (c1=2; c1<=MaxAmount; c1++)
    {
        CoinSet[1] = c1;
        TotalCoins = MakeChangeProblem(MaxAmount, CoinSet);
        
        /* Only print sets which are better than found so far */
        if (TotalCoins <= MinAmount)
        {
            MinAmount = TotalCoins;
            printf("1 %3u %10u\n", c1, TotalCoins);
        }
    }
    return 0;
}

INTTYPE MakeChangeProblem(const INTTYPE Total, const INTTYPE *CoinSet)
{
    /* We use a static allocation here, which is faster than dynamic */
    INTTYPE MinCoins[MaxAmount+1];
    INTTYPE i, j, T;
        
    /* This part is taken from the web */
    /* http://codereview.stackexchange.com/questions/92811/find-the-minimum-number-of-coins/92820 */
    MinCoins[0] = 0;
    for (j=1; j<=Total; j++)
    {
        MinCoins[j] = INTMAX;
    }

    for (i = 0; i < NrCoins; i++)
    {
        for (j = CoinSet[i]; j <= Total; j++)
        {
            T = MinCoins[j - CoinSet[i]] + 1;
            if (T < MinCoins[j])
            {
                MinCoins[j] = T;
            }
        }
    }
    
    T = 0;
    for (j=1; j<=Total; j++)
    {
        T += MinCoins[j];
    }
    return T;
}