किसी दिए गए सेंट राशि के लिए, यदि सभी ट्यूबों में 64 हो, तो सिक्का-ट्यूबों की संख्या को कम करें, लेकिन

Question

संपादित करें: अगर कोई प्रसिद्ध सिक्का में एक समझाया गया रिकर्सिव उत्तर (एक लिंक करेगा) प्रदान कर सकता है परिवर्तन समस्या यह एक बहुत

---

मदद मिलेगी एक दिया प्रतिशत राशि के लिए, सिक्का ट्यूबों की संख्या को कम सभी ट्यूबों 64 सिक्के पकड़ कर सकते हैं।

प्रत्येक ट्यूब केवल एक ही प्रकार का सिक्का रख सकती है।

प्रत्येक ट्यूब को पूरी तरह से भरने की आवश्यकता नहीं है।

---

उदा। अमेरिकी सिक्कों के लिए मात्रा में $ 0.01, $ 0.05, $ 0.10, $ 0.25, $ 0.50, और $ 1,00

6 सेंट एक एकल ट्यूब में 6 1cent सिक्के के रूप में किया जा सकता है,

25 सेंट एक एकल के साथ एक ट्यूब हो सकता है हो सकता है 25 सी सिक्का या पांच 5 सी सिक्कों वाली एक ट्यूब।

65 सेंट 13 5 सी सिक्कों के रूप में किया जाएगा, क्योंकि 65 1 सी सिक्कों को 2 ट्यूबों का उपयोग करने की आवश्यकता होगी।

---

मैं एक Minecraft प्लगइन लिखने का प्रयास कर रहा हूं, और मुझे इस एल्गोरिदम के साथ बहुत कठिनाई हो रही है।

Answer 1

कुछ इस तरह:

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

एक लुकअप तालिका एक अच्छा तरीका है। कुछ मिलीसेकेंड में

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 रन है, तो आप डिस्क पर संग्रहीत करने के लिए की जरूरत नहीं है:

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

तालिका गणना करने के लिए, तो आप इस इस्तेमाल कर सकते हैं।

उदाहरण:

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

संख्या सिक्कों की संख्या मतलब है। एन सिक्के (एन + 63)/64 ट्यूबों में रखा जा सकता है।

Answer 3

यहां एक recursive, 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 

करने के लिए बेहद चल समय में सुधार, आप देख सकते हैं कि वर्तमान T[sum] पहले से ही मूल्यांकन किया गया है। इस चेक को जोड़ने से dynamic programming नामक दृष्टिकोण पूरा हो जाता है।

* current-tubes is better than best-tubes कम ट्यूबों का उपयोग कर रहा है, या कम सिक्कों के साथ ट्यूबों की एक ही संख्या का उपयोग कर या ट्यूबों की एक ही संख्या का उपयोग कर, लेकिन ट्यूबों जो बड़े मूल्य रखते हैं। यह कार्रवाई भाग में लालची है।