C++의 비트마스킹 및 동적 프로그래밍

<시간/>

먼저 비트마스킹과 동적 프로그래밍에 대해 배운 다음 구현과 관련된 질문을 해결할 관련 문제를 해결할 것입니다.

비트마스크 마스크라고도 함 우리 컬렉션의 하위 집합을 인코딩하는 N 비트 시퀀스입니다. 마스크의 요소는 설정되거나 설정되지 않을 수 있습니다(즉, 0 또는 1). 이것은 비트마스크에서 선택된 요소의 가용성을 나타냅니다. 예를 들어, 마스크의 i번째 비트가 설정되면 요소 i를 부분 집합에서 사용할 수 있습니다. N 요소 집합의 경우 2^N 이 있을 수 있습니다. 하위 집합에 해당하는 각각을 마스크합니다.

따라서 문제를 해결하기 위해 마스크를 시작합니다. 즉, 하위 집합이 값을 할당한 다음 이전 마스크의 값을 사용하여 추가 마스크의 값을 찾습니다. 이것을 사용하여 우리는 마침내 메인 세트의 값을 계산할 수 있을 것입니다.

마스크에 대한 최적의 솔루션을 계산하기 위해 가능한 모든 방법으로 하나의 요소를 제거하고 최종 솔루션에 기여할 모든 값을 계산합니다.

동적 프로그래밍

동적 프로그래밍은 하위 문제를 해결하고 다른 중첩 하위 문제에서 사용하기 위해 해당 솔루션을 저장하는 최적화 방법입니다.

이제 비트 마스킹 및 동적 프로그래밍을 사용하여 해결할 문제를 살펴보겠습니다.

문제

1에서 50까지의 숫자가 있는 50개의 모자가 있습니다. N명의 사람들이 컬렉션에 이러한 모자 중 일부를 가지고 있습니다. 어느 날 그들은 모두 모자를 쓰고 파티에 참석합니다. 그러나 모두 독특하게 보일 필요가 있으므로 각각 다른 번호의 모자를 착용하기로 결정했습니다. 우리는 n명의 사람들과 그들의 컬렉션에 있는 모자 번호를 받습니다. 우리의 임무는 모두가 독특하게 보이도록 모자를 착용할 수 있는 총 방법의 수를 찾는 것입니다.

문제에서 첫 번째 줄에는 사람의 수인 값 n이 포함되어 있습니다. 다음 n줄에는 컬렉션이 포함되어 있습니다.

입력 -

출력 -

설명 -

가능한 모든 방법은 (4, 25, 45) , (4, 25, 10), (45, 25, 10), (10, 25, 45)입니다.

방법의 수가 많을 수 있으므로 출력은 1000000007 형식이어야 합니다.

이 문제를 해결하기 위해 간단한 솔루션은 모자를 사용하는 사람들의 가능한 모든 조합을 찾는 것입니다. 첫 번째 세트부터 시작하여 나머지 세트를 반복합니다. 하지만 이 솔루션은 최적화되어 있지 않습니다.

더 나은 솔루션은 Bitmasking과 DP를 사용하여 10인용 크기 210의 마스크를 만드는 것입니다. 크기가 51인 대문자 벡터입니다. 그러면 여러 가지 방법으로 반복됩니다.

예시

솔루션 구현을 보여주는 프로그램 -

#include<bits/stdc++.h>
using namespace std;
vector<int> caps[101];
int dp[1025][101];
int allmask;
long long int uniqueCaps(int mask, int i) {
   if (mask == allmask) return 1;
   if (i > 100) return 0;
   if (dp[mask][i] != -1) return dp[mask][i];
   long long int ways = uniqueCaps(mask, i+1);
   int size = caps[i].size();
   for (int j = 0; j < size; j++) {
      if (mask & (1 << caps[i][j])) continue;
         else ways += uniqueCaps(mask | (1 << caps[i][j]), i+1);
         ways %= (1000000007);
      }
      return dp[mask][i] = ways;
   }
int main() {
   int n = 3;
   // Collection of person 1
   caps[4].push_back(0);
   caps[45].push_back(0);
   caps[10].push_back(0);
   // Collection of person 2
   caps[25].push_back(1);
   // Collection of person 3
   caps[45].push_back(2);
   caps[10].push_back(2);
   allmask = (1 << n) - 1;
   memset(dp, -1, sizeof dp);
   cout<<"The number of ways the person can wear unique cap in party is:\t"<<uniqueCaps(0, 1);
   return 0;
}

출력

The number of ways the person can wear unique cap in party is: 4