Für eine bestimmte Cent-Menge, minimieren Sie die Anzahl der Münzröhren, wenn alle Röhren 64 halten, aber nicht gefüllt werden müssen

Edit: Wenn jemand eine erklärte rekursive Antwort (ein Link würde tun) auf die berühmte Münze bieten könnte Änderung Problem würde diesFür eine bestimmte Cent-Menge, minimieren Sie die Anzahl der Münzröhren, wenn alle Röhren 64 halten, aber nicht gefüllt werden müssen

Für eine gegebene Menge cent helfen, eine Menge, die Anzahl der Münzenröhren zu minimieren, wenn alle Rohre 64 Münzen aufnehmen kann.

jedes Rohr kann nur eine einzige Art von Münze halten.

jedes Rohr muss nicht vollständig gefüllt werden.

z.B. für amerikanische Münzen würden die Mengen $ 0.01, $ 0.05, $ 0.10, $ 0.25, $ 0,50 und $ 1,00

6 Cent als 6 1cent Münzen in einem einzigen Rohr,

25 Cent könnte eine Röhre mit einem einzigen durchgeführt werden könnte sein, 25c Münze oder eine Tube mit fünf 5c Münzen.

65 Cent wäre als 13 5c Münzen, als 65 1c Münzen müssten 2 Röhren verwendet werden.

Ich versuche, ein Minecraft-Plugin zu schreiben, und ich habe eine Menge Schwierigkeiten mit diesem Algorithmus.

Quelle

2012-09-09 Andreas Pettifer

Es scheint, dass ein einfacher Brute-Force-Ansatz gut genug sein sollte, es sei denn, Sie wollen mit sehr großen Geldsummen umgehen? –

Ehrlich? Ich bin sehr neu im Programmieren und habe keine Ahnung, wo ich anfangen soll. Ich habe versucht, darüber nachzudenken, irgendwie einen gierigen Ansatz zu modifizieren, hatte über das Brute-Forcing nachgedacht, aber ich hatte Probleme, die Kombinationen zu bekommen oder einen zu finden Beispiel (wie man Kombinationen von Münzen von einem Betrag erhält), die ich verstehen konnte. Ich habe gerade ein Beispiel für Stackoverflow gefunden, dem ich folgen kann, also werde ich in Kürze updaten. –

Könnte das 25 Cent Beispiel mit 25 1c Münzen in einer Röhre gemacht werden? –

etwas wie folgt aus:

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

Quelle

2012-09-10 05:21:39 Herokiller

Warum wird p == 5 überprüft? Hast du den Code ausgeführt? –

weil für a [5] = 1 gibt es nur eine gültige Variante, um die Münzen zu erhalten. nein Ich habe den Code nicht ausgeführt – Herokiller

Eine Lookup-Tabelle ist eine gute Methode.

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 läuft in wenigen Millisekunden, so dass Sie es auf die Festplatte nicht speichern müssen:

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

die Tabelle zu berechnen, können Sie diese verwenden.

Beispiel:

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

die Zahlen bedeuten die Anzahl der Münzen. N Münzen können in (N + 63)/64 Röhren gelegt werden.

Quelle

2012-09-10 08:30:55

Hier ist ein recursive, heuristic und greedy Algorithmus.

In dem Array T enthält jeder T[i] ein Array von 6 ganzen Zahlen. Wenn die angegebene Summe 65 ist, dann rufen Sie tubes(65) und dann print T[65] an.

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

Um erheblich die Laufzeit verbessern, können Sie überprüfen, ob die aktuelle T[sum] bereits bewertet worden. Durch Hinzufügen dieser Überprüfung wird der Ansatz dynamic programming abgeschlossen.

* current-tubes is better than best-tubes verwendet weniger Röhren, oder die gleiche Anzahl von Röhren mit weniger Münzen oder mit der gleichen Anzahl von Röhren, aber Röhren, die größere Werte halten. Dies ist der gierige in Aktion Teil.

Quelle

2012-09-10 14:29:11

Für eine bestimmte Cent-Menge, minimieren Sie die Anzahl der Münzröhren, wenn alle Röhren 64 halten, aber nicht gefüllt werden müssen

Antwort

Verwandte Themen