Per una quantità di centesimo, ridurre il numero di provette se tutte le provette contengono 64 ma non devono essere riempite

Question

Modifica: Se qualcuno potrebbe fornire una risposta ricorsiva spiegata (un collegamento farebbe) alla famosa moneta cambiamento problema questo aiuterebbe molto

---

Per una data quantità centesimo, minimizzare il numero di monete tubi se tutti i tubi possono contenere 64 monete.

Ogni tubo può SOLO contenere un singolo tipo di moneta.

ogni tubo NON deve essere riempito completamente.

---

ad es. per american monete importi sarebbero $ 0,01, $ 0,05, $ 0,10, $ 0,25, $ 0,50, e $ 1,00

6 centesimi potuto essere fatti come 6 1 cent monete in un unico tubo,

25 centesimi potrebbe essere un tubo con una singola Moneta da 25c o un tubo con cinque monete 5c.

65 centesimi si farebbero come 13 monete da 5c, in quanto 65 monete da 1c dovrebbero utilizzare 2 tubi.

---

Sto tentando di scrivere un plug-in Minecraft e sto avendo MOLTA difficoltà con questo algoritmo.

Answer 1

qualcosa di simile:

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 tabella di ricerca è un buon metodo.

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

Per calcolare la tabella, è possibile utilizzare questo:

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 viene eseguito in pochi millisecondi, in modo da non dover memorizzare su disco.

Esempio:

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

I numeri significa il numero di monete. N monete (N + 63)/64 tubi.

Answer 3

Ecco un algoritmo recursive, heuristic e greedy.

Nell'array T, ogni T[i] contiene un array di 6 numeri interi.

Se la somma data è 65, si chiama tubes(65) e quindi 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 

Per enormemente migliorare il tempo di esecuzione, è possibile controllare se la corrente T[sum] è già stato valutato. L'aggiunta di questo controllo completa l'approccio chiamato dynamic programming.

* current-tubes is better than best-tubes utilizza meno tubi o utilizza lo stesso numero di tubi con meno monete o utilizzando lo stesso numero di tubi ma tubi che contengono valori maggiori. Questa è la parte golosa in azione.