동적 프로그래밍 알고리즘 N, K 문제

StackOverflow https://stackoverflow.com/questions/2245100

문제

두 개의 양수 n과 k를 취하고 n에서 k 자리를 제거하여 N을 다른 숫자로 변환하여 얻을 수있는 가장 큰 숫자를 계산하는 알고리즘.

EX의 경우 N = 12345 및 k = 3을 가지고 있다고 가정 해 봅시다. 따라서 N에서 3 자리를 제거함으로써 얻을 수있는 가장 큰 숫자는 45입니다 (다른 변환은 12, 15, 35이지만 45는 가장 큰 것입니다). 또한 N에서 숫자 순서를 변경할 수 없습니다 (따라서 54는 해결책이 아닙니다). 또 다른 예는 n = 66621542 및 k = 3이므로 솔루션은 66654가됩니다.

나는 이것이 역동적 인 프로그래밍 관련 문제라는 것을 알고 있으며 그것을 해결하는 것에 대한 아이디어를 얻을 수 없습니다. 2 일 동안이 문제를 해결해야하므로 도움이 감사합니다. 당신이 나를 위해 이것을 해결하고 싶지 않다면 당신은 그럴 필요가 없지만 비슷한 문제에 대해 더 많이 읽을 수있는 트릭이나 적어도 일부 자료를 알려주세요.

미리 감사드립니다.

도움이 되었습니까?

해결책

역동적 인 프로그래밍 문제를 해결하기위한 요령은 일반적으로 솔루션의 구조가 어떻게 보이는지, 더 구체적으로는 전시하는 경우 최적의 하위 구조.

이 경우, n = 12345 및 k = 3 인 최적의 솔루션은 용액의 일부로서 n = 12345 및 k = 2에 대한 최적의 솔루션을 가질 것으로 보인다. 이것이 보유하고 있다고 스스로에게 확신 할 수 있다면, 문제에 대한 해결책을 재귀 적으로 표현할 수 있어야합니다. 그런 다음 MEMOISATION 또는 상향식으로 이것을 구현하십시오.

다른 팁

이것은 O (l)에서 해결할 수 있습니다. 여기서 l = 숫자 수입니다. 스택을 사용 하여이 작업을 수행 할 수있을 때 복잡한 DP 공식을 사용하는 이유 :

for : 66621542 스택에 숫자를 추가하고 스택에 l -k 숫자가 적거나 동일하지만 66621. 이제 스택에서 숫자를 제거하고 현재 읽기 숫자보다 작고 현재 숫자를 스택:

5 : 5> 2를 읽고 스택에서 1을 팝하십시오. 5> 2, 팝 2. 5 : 6665 읽기 4 : 스택이 가득 차 있지 않습니다. 4 : 66654 읽기 2 : 2 <4, 아무것도하지 마십시오.

한 번 더 조건이 필요합니다. 숫자에 숫자가 남아있는 것보다 스택에서 더 많은 항목을 꺼내지 마십시오. 그렇지 않으면 솔루션이 불완전합니다!

또 다른 예 : 12345 l = 5, k = 3 Put L -K = 2 자리 숫자 : 12

읽기 3, 3> 2, Pop 2, 3> 1, Pop 1, Put 3. Stack : 3 읽기 4, 4> 3, Pop 3, Put 4 : 4 읽기 5 : 5> 4. 4, 그렇지 않으면 숫자가 충분하지 않습니다. 따라서 5 : 45를 밀어냅니다.

역동적 인 프로그래밍 문제를 해결하려면 반복되는 하위 분해 문제를 해결해야합니다.

문제를 (n, k)로 정의하면 n에서 k 숫자를 제거하여 가능한 가장 큰 숫자를 반환합니다.

이것으로부터 간단한 재귀 알고리즘을 정의 할 수 있습니다.

예제, A (12345, 3) = max {A (2345, 2), A (1345, 2), A (1245, 2), A (1234, 2)}

보다 일반적으로, a (n, k) = max {a (1 자리가 제거 된 n, k -1)}

그리고 당신은 기본 케이스가 (n, 0) = n입니다.

이 접근법을 사용하면 N과 K의 값을 캐시하는 테이블을 만들 수 있습니다.

int A(int n, int k)
{
  typedef std::pair<int, int> input;
  static std::map<input, int> cache;

  if (k == 0) return n;

  input i(n, k);
  if (cache.find(i) != cache.end())
    return cache[i];

  cache[i] = /* ... as above ... */

  return cache[i];
}

이제 이것은 간단한 솔루션이지만 매우 작은 1 차원 캐시와 함께 작동하는 더 나은 솔루션이 있습니다. "문자열 n과 정수 k를 주어 주면 길이 k의 n에서 사전 가장 큰 후속을 찾으십시오"라는 질문을 다시 말해주십시오. 이것은 본질적으로 문제가있는 것이며 솔루션은 훨씬 더 간단합니다.

이제 다른 기능을 정의 할 수 있습니다 B (I, J), 가장 큰 사전 서열을 제공합니다 (I -J), 첫 번째 만 사용합니다 나 숫자 N (다시 말해서, 제거 제이 첫 번째 숫자 나 숫자 N).

예제를 다시 사용하면 다음과 같습니다.

b (1, 0) = 1

B (2, 0) = 12

B (3, 0) = 123

B (3, 1) = 23

B (3, 2) = 3

등.

약간의 사고로 우리는 재발 관계를 찾을 수 있습니다.

b (i, j) = max (10b (i-1, j) + n나 , B (I-1, J-1)))

또는 if j = i 그 다음에 B (I, J) = B (I-1, J-1)

그리고 b (0, 0) = 0

또한 위와 매우 유사한 방식으로 코딩 할 수 있습니다.

동적 프로그래밍 솔루션의 가장 중요한 두 가지 요소는 다음과 같습니다.

  1. 권리를 정의합니다 하위 문제
  2. 정의 a 재발 관계 하위 프로젝트에 대한 답과 작은 하위 프로젝트에 대한 답변 사이
  3. 발견 기본 케이스, 다른 답변에 의존하지 않는 가장 작은 하위 프로젝트
  4. 알아내는 것 스캔 순서 하위 프로젝트를 해결해야합니다 (따라서 초기화되지 않은 데이터를 기반으로 재발 관계를 사용하지 마십시오)

당신은 당신이

  • 답이 필요한 문제는 그 중 하나입니다.
  • 기본 케이스는 실제로 사소합니다
  • 재발은 평가하기 쉽습니다
  • 스캔 순서는 간단합니다

귀하의 경우, 하위 문제를 지정하는 것이 간단합니다. 이것은 아마도 숙제이기 때문에, 나는 당신에게 힌트를 줄 것입니다 N이 시작할 숫자가 적을 수 있기를 바랍니다..

다음은 다음과 같습니다.

왼쪽에서 첫 k + 1 자리를 고려하십시오. 가장 큰 것을 찾아서 찾아 왼쪽으로 숫자를 제거하십시오. 가장 큰 숫자 중 두 개가 있으면 가장 왼쪽 숫자를 찾아 그 왼쪽의 숫자를 제거하십시오. 제거 된 숫자 (이름 j)의 수를 저장하십시오.

K와 N 및 K+1 -J와 같은 새 번호로 동일한 작업을 수행하십시오. K+1 -J가 1과 같을 때까지 (오해하지 않으면) 이것을하십시오.

당신이 끝나는 숫자는 당신이 찾고있는 숫자가 될 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top