For a given cent amount, minimize the number of coin-tubes if all tubes hold 64 but do not need to be filled

Question

Edit: If someone could provide an explained recursive answer(a link would do) to the famous coin change problem this would help a LOT

---

For a given cent amount, minimize the number of coin-tubes if all tubes can hold 64 coins.

each tube can ONLY hold a single type of coin.

each tube does NOT need to be fully filled.

---

e.g. for american coins the amounts would be $0.01, $0.05, $0.10, $0.25, $0.50, and $1.00

6 cents could be done as 6 1cent coins in a single tube,

25 cents could be a tube with a single 25c coin or a tube with five 5c coins.

65 cents would be done as 13 5c coins, as 65 1c coins would need to use 2 tubes.

---

I'm attempting to write a minecraft plugin, and I am having a LOT of difficulty with this algorithm.

Answer 1

A lookup table is a good method.

int[] Coins = new[] { 100, 50, 25, 10, 5, 1 };
int[,] Table = new int[6,6400];

/// Calculate the number of coins of each type that minimizes the number of
/// tubes used.
int[] Tubes(int cents)
{
    int[] counts = new int[Coins.Length];
    if (cents >= 6400)
    {
        counts[0] += (cents / 6400) * 64; // number of coins in filled $1-tubes
        cents %= 6400;
    }
    for (int i = 0; i < Coins.Length; i++)
    {
        int count = Table[i, cents]; // N coins in (N + 63) / 64 tubes
        counts[i] += count;
        cents -= count * Coins[i];
    }
    return cents;
}

To calculate the table, you could use this:

void CalculateTable()
{
    for (int i = Coins.Length-1; i >= 0; i--)
    {
        int coin = Coins[i];
        for (int cents = 0; cents < 6400; cents++)
        {
            if (i == Coins.Length-1)
            {
                // The 1 cent coin can't be divided further
                Table[i,cents] = cents;
            }
            else
            {
                // Find the count that minimizes the number of tubes.
                int n = cents / coin;
                int bestTubes = -1;
                int bestCount = 0;
                for (int count = cents / coin; count >= 0; count--)
                {
                    int cents1 = cents - count * coin;
                    int tubes = (count + 63) / 64;
                    // Use the algorithm from Tubes() above, to optimize the
                    // lesser coins.
                    for (int j = i+1; j < Coins.Length; j++)
                    {
                        int count1 = Table[j, cents1];
                        cents1 -= count1 * Coins[j];
                        tubes += (count1 + 63) / 64;
                    }
                    if (bestTubes == -1 || tubes < bestTubes)
                    {
                        bestTubes = tubes;
                        bestCount = count;
                    }
                }
                // Store the result
                Table[i,cents] = bestCount;
            }
        }
    }
}

CalculateTable runs in a few milliseconds, so you don't have to store it to disk.

Example:

Tubes(3149)  -> [ 31,  0,  0,  0,  0, 49]
Tubes (3150)  -> [  0, 63,  0,  0,  0,  0]
Tubes (31500) -> [315,  0,  0,  0,  0,  0]

The numbers mean the number of coins. N coins could be put into (N + 63)/64 tubes.