C++ 프로그램: 코인 결제를 사용하여 n에 도달하는 데 필요한 작업 수를 계산합니다.

N, A, B, C, D라는 5개의 숫자가 있다고 가정합니다. 숫자 0으로 시작해서 N으로 끝납니다. 다음과 같이 특정 개수의 코인으로 숫자를 변경할 수 있습니다.

• 숫자에 2를 곱하고 A 코인을 지불합니다.
• 숫자에 3을 곱하고 B 코인을 지불합니다.
• 숫자에 5를 곱하고 C 코인을 지불합니다.
• 숫자 1을 늘리거나 줄이고, D 코인을 지불하세요

이러한 작업은 횟수와 순서에 관계없이 수행할 수 있습니다. N에 도달하는 데 필요한 최소 코인 수를 찾아야 합니다. 따라서 입력이 N = 11, B = 2, D = 8이면 처음에 x는 19가 됩니다. 0.

코인 8개를 사용하여 x를 1만큼 늘립니다(x=1).

1개의 동전을 사용하여 x에 2를 곱하세요(x=2).

2개의 동전을 사용하여 x에 5를 곱하세요(x=10).

코인 8개를 사용하여 1(x=11) 늘립니다.

Steps

이 문제를 해결하기 위해 다음 단계를 따릅니다.

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

Input

11, 1, 2, 2, 8

Output

19

위 내용은 C++ 프로그램: 코인 결제를 사용하여 n에 도달하는 데 필요한 작업 수를 계산합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!