Por un centavo dado, minimice el número de tubos de monedas si todos los tubos tienen 64 pero no es necesario que se llenen

Question

Editar: Si alguien pudiera proporcionar una respuesta recursiva explicada (un enlace haría) a la famosa moneda problema del cambio de esto sería una gran ayuda

---

Para una cantidad dada ciento, reducir al mínimo el número de monedas tubos si todos los tubos puede contener 64 monedas.

cada tubo SÓLO puede contener un solo tipo de moneda.

cada tubo NO necesita llenarse por completo.

---

e.g. para monedas americanas las cantidades serían de $ 0,01, $ 0,05, $ 0,10, $ 0,25, $ 0,50, y $ 1.00

6 centavos podría hacerse como 6 1cent monedas en un solo tubo,

25 centavos podrían ser un tubo con una sola Moneda 25c o un tubo con cinco monedas de 5c.

65 centavos se harían en 13 monedas de 5c, ya que 65 monedas de 1c necesitarían usar 2 tubos.

---

Estoy intentando escribir un plugin de Minecraft, y estoy teniendo muchas dificultades con este algoritmo.

Answer 1

algo como esto:

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); 
} 

Answer 2

Una tabla de búsqueda es un buen método.

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; 
} 

Para el cálculo de la tabla, se puede usar esto:

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 carreras en unos pocos milisegundos, por lo que no tiene que almacenar en el disco.

Ejemplo:

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

Los números significa el número de monedas. N monedas podrían ponerse en (N + 63)/64 tubos.

Answer 3

Aquí hay un algoritmo recursive, heuristic y greedy.

En la matriz T, cada T[i] contiene una matriz de 6 enteros.

Si la suma dada es 65, entonces llama al tubes(65) y luego al 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 

Para enormemente mejorar el tiempo de ejecución, se puede comprobar si la corriente T[sum] ya ha sido evaluado. Agregar esta verificación completa el enfoque llamado dynamic programming.

* current-tubes is better than best-tubes usa menos tubos, o usa la misma cantidad de tubos con menos monedas o usa la misma cantidad de tubos pero tubos que tienen valores más grandes. Esta es la parte codiciosa en acción.