對於給定的美分數量，如果所有管子可以放置64個，但不需要填充，則儘量減少投幣管的數量

編輯：如果有人能夠向着名的硬幣提供解釋的遞歸答案（鏈接將做）變化的問題，這將有很大的幫助對於給定的美分數量，如果所有管子可以放置64個，但不需要填充，則儘量減少投幣管的數量

對於給定的分額，減少硬幣管的數量，如果所有的管子可容納64個硬幣。

每個管僅能保持單個類型的硬幣。

各管並不需要完全充滿。

例如，爲美國硬幣的金額將是$ 0.01 $ 0.05 $ 0.10，$ 0.25，$ 0.50，和$ 1.00包裝

6美分可以在單個試管中進行如圖6枚1美分硬幣，

25美分可以是具有單一的管25c硬幣或與五個5c硬幣的管。

65美分將被完成爲13枚5c的硬幣，如65個1C硬幣將需要使用2個試管。

我試圖寫一個minecraft插件，而且我在這個算法上遇到很多困難。

來源

2012-09-09 Andreas Pettifer

看來，一個簡單的蠻力方法應該足夠好，除非你想要處理大量的金錢？ –

老實說？我對編程非常陌生，幾乎不知道從哪裏開始，我試圖想方設法修改一個貪婪的方法，曾經考慮過蠻橫的問題，但是我遇到了麻煩，即使得到了組合的數量或找到了我可以理解的例子（關於如何從金額中獲得硬幣的組合）。我剛剛在stackoverflow上找到了一個可以遵循的例子，所以我馬上就會更新。 –

25美分的例子可以在一個管中使用25個1c硬幣完成嗎？ –

是這樣的：

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

來源

2012-09-10 05:21:39 Herokiller

爲什麼要檢查p == 5。你有沒有運行代碼？ –

，因爲對於[5] = 1，只有1個有效的變體來獲得硬幣。不，我沒有運行代碼 – Herokiller

查找表是一個很好的方法。在幾毫秒內

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管。

來源

2012-09-10 08:30:55

這裏是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正在使用較少的管子，或者使用相同數量的管子，使用較少的硬幣或使用相同數量的管子，但使用的管子數量較大。這是貪婪的行動部分。

來源

2012-09-10 14:29:11

對於給定的美分數量，如果所有管子可以放置64個，但不需要填充，則儘量減少投幣管的數量

回答

相關問題