5

編集：誰かが有名なコイン交換の問題に説明された再帰的な答えを提供できれば（リンクはそうするでしょう）、これは多くの人を助けるでしょう

すべてのチューブが64枚のコインを保持できる場合は、一定のセント額でコインチューブの数を最小限に抑えます。

各チューブは1種類のコインしか保持できません。

各チューブを完全に満たす必要はありません。

たとえば、アメリカのコインの場合、金額は$ 0.01、$ 0.05、$ 0.10、$ 0.25、$ 0.50、および$1.00になります。

6セントは、1本のチューブに6枚の1セント硬貨として入れることができます。

25セントは、1枚の25cコインが入ったチューブ、または5枚の5cコインが入ったチューブの場合があります。

65セントは135cコインとして行われ、651cコインは2本のチューブを使用する必要があります。

Minecraftプラグインを作成しようとしていますが、このアルゴリズムで多くの問題が発生しています。

4

3 に答える 3

1

ルックアップ テーブルは良い方法です。

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

テーブルを計算するには、これを使用できます。

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数ミリ秒で実行されるため、ディスクに保存する必要はありません。

例：

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

数字はコインの枚数です。N 個のコインを ( N + 63)/64 チューブに入れることができます。

于 2012-09-10T08:30:55.340 に答える
0

これは、再帰的でヒューリスティックで貪欲なアルゴリズムです。

arrayTでは、それぞれ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]改善するために、電流がすでに評価されているかどうかを確認できます。このチェックを追加すると、動的計画法と呼ばれるアプローチが完成します。

*current-tubes is better than best-tubesより少ないチューブを使用するか、同じ数のチューブを使用してより少ないコインを使用するか、または同じ数のチューブを使用してより大きな値を保持するチューブを使用します。これは貪欲な行動の部分です。

于 2012-09-10T14:29:11.883 に答える
0

このようなもの：

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-10T05:21:39.207 に答える