Geek asks and answers

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

Edit: If someone can provide an explained recursive answer (the link will do) to a known problem with changing a coin, this will help LOT

With a given quantity value, minimize the number of coin tubes if all tubes can contain 64 coins.

Each tube can ONLY hold one type of coin.

each tube must NOT be completely filled.

eg. for American coins, the amount will be $ 0.01, $ 0.05, $ 0.10, $ 0.25, $ 0.50 and $ 1.00.

6 cents can be made in the form of 6 1 price coins in one pipe,

25 cents can be a tube with one 25-centimeter coin or a tube with five coins 5c.

65 cents will be made as 13 5c coins, since 65 1c coins will have to use 2 tubes.

I am trying to write a minecraft plugin and I have many problems with this algorithm.

+5
source share
3 answers

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 compute a table, you can 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 do not need to store it on 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 indicate the number of coins. N coins could be placed in (N + 63) / 64 tubes.

+1
source

something like that:

a[0] = 100; //cents
a[1] = 50; a[2] = 25; a[3] = 10; a[4] = 5; a[5] = 1;

cnt[6]; //array to store how much coins of type i you use;


void rec(sum_left, p /* position in a array */) {
   if ( p == 5 ) {
      cnt[5] = sum_left;
      //count how many tubes are used by cnt array, update current answer if neccessary;
      return;
   }
   for ( int i = 0; i <= sum_left/a[p]; i++ )
      //take i coins of type a[p]
      rec(sum_left - i*a[i], p+1);
}

int main() {
   rec(sum, 0);
}
0
source

, heuristic greedy.

T T[i] 6 .

65, tubes(65), print T[65].

coins[1..6] = {1, 5, 10, 25, 50, 100}

tubes(sum)
    if sum < coins[1]
        return
    for i = 1 to 6
        tubes(sum - coins[i])
    best-tubes[1..6] = {64, 64, 64, 64, 64, 64}
    for i = 1 to 6
        if sum - coins[i] >= 0
            current-tubes[1..6] = copy of T[sum - coins[i]]
            if current-tubes[i] < 64
                current-tubes[i] += 1
                if current-tubes is better than best-tubes*
                    best-tubes = current-tubes
    T[sum] = best-tubes

In significantly improving the working time, you can check whether the current one has already been evaluated T[sum]. Adding this check completes an approach called dynamic programming .

* current-tubes is better than best-tubesuses fewer handsets or uses the same number of handsets with fewer coins or uses the same number of handsets, but handsets that contain larger values. This is the greedy part in action.

0
source

More articles:


All Articles