C++ プログラム: コイン支払いを使用して n に到達するために必要な操作の数を計算します。

N、A、B、C、D という 5 つの数字があるとします。数字の 0 から始まり N で終わります。特定のコインを使用して数値を変更することができます。具体的な操作は次のとおりです:

• 数値を 2 倍して A コインを支払います
• 数値を 3 倍して、 B コインを支払う コイン
• 数字を 5 倍し、C コインを支払う
• 数字を 1 ずつ増減し、D コインを支払う

これは任意で実行できますこれらの操作の回数と順序は任意です。 N に到達するために必要なコインの最小数を見つける必要があります

したがって、入力が N = 11、A = 1、B = 2、C = 2、D = 8 の場合、出力は 19 になります。なぜなら、最初の x は 0 だからです。

8 コインを使用して x を 1 増やします (x=1)。

1 コインを使用して x を 2 倍します (x=2)。

コイン 2 枚を使って x を 5 倍します (x=10)。

8 コインを使用して 1 増やします (x=11)。

手順

この問題を解決するには、次の手順に従います。

Define one map f for integer type key and value
Define one map vis for integer type key and Boolean type value
Define a function calc, this will take n
if n is zero, then:
   return 0
if n is in vis, then:
   return f[n]
vis[n] := 1
res := calc(n / 2) + n mod 2 * d + a
if n mod 2 is non-zero, then:
   res := minimum of res and calc((n / 2 + 1) + (2 - n mod 2)) * d + a)
res := minimum of res and calc(n / 3) + n mod 3 * d + b
if n mod 3 is non-zero, then:
   res := minimum of res and calc((n / 3 + 1) + (3 - n mod 3)) * d + b)
res := minimum of res and calc(n / 5) + n mod 5 * d + c
if n mod 5 is non-zero, then:
   res := minimum of res and calc((n / 5 + 1) + (5 - n mod 5))
if (res - 1) / n + 1 > d, then:
   res := n * d
return f[n] = res
From the main method, set a, b, c and d, and call calc(n)

Example

よりよく理解するために、次の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int a, b, c, d;
map<long, long> f;
map<long, bool> vis;

long calc(long n){
   if (!n)
      return 0;
   if (vis.find(n) != vis.end())
      return f[n];
   vis[n] = 1;
   long res = calc(n / 2) + n % 2 * d + a;
   if (n % 2)
      res = min(res, calc(n / 2 + 1) + (2 - n % 2) * d + a);
   res = min(res, calc(n / 3) + n % 3 * d + b);
   if (n % 3)
      res = min(res, calc(n / 3 + 1) + (3 - n % 3) * d + b);
   res = min(res, calc(n / 5) + n % 5 * d + c);
   if (n % 5)
      res = min(res, calc(n / 5 + 1) + (5 - n % 5) * d + c);
   if ((res - 1) / n + 1 > d)
      res = n * d;
   return f[n] = res;
}
int solve(int N, int A, int B, int C, int D){
   a = A;
   b = B;
   c = C;
   d = D;
   return calc(N);
}
int main(){
   int N = 11;
   int A = 1;
   int B = 2;
   int C = 2;
   int D = 8;
   cout << solve(N, A, B, C, D) << endl;
}

入力

11, 1, 2, 2, 8

出力

19

以上がC++ プログラム: コイン支払いを使用して n に到達するために必要な操作の数を計算します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。