이 문제에서는 크기가 2 n 인 배열 arr[]가 제공됩니다. . 우리의 임무는 그것을 풀기 위해 동적 프로그래밍을 사용하여 부분 집합에 대한 합을 찾는 프로그램을 만드는 것입니다.
함수를 계산해야 합니다. F(x) =Σ Ai 모든 x에 대해 x&i ==i가 되도록. 즉, i는 x의 비트 부분집합입니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
입력: A[] ={5, 7, 1, 9}, n =2
출력: 5 12 6 22
설명: n =2 의 경우 x 값은 4개입니다. 0, 1, 2, 3입니다.
이제 함수의 값을 계산합니다.
F(0) =A0 =5
F(1) =A0 + A1 =5 + 7 =12
F(2) =A0 + A2 =5 + 1 =6
F(3) =A0 + A1 + A2 + A3 =5 + 7 + 1 + 9 =22
동적 프로그래밍 을 사용하여 이 문제에 대한 해결책 우리는 마스크를 살펴보고 모든 마스크의 비트 단위 하위 집합을 찾습니다. 반복 횟수를 줄이는 동적 프로그래밍을 사용하여 비트 하위 집합을 저장합니다. 비트가 설정되었거나 비트가 설정되지 않은 인덱스는 2
n
이 방문합니다. 마스크를 두 번 이상 사용합니다.
i 인덱스의 비트를 기반으로 반복됩니다.
i번째 비트가 설정되었을 때 :
DP(마스크, i) =DP(마스크, i-1) U DP(마스크 2 i , i-1)
i번째 비트가 설정되지 않은 경우 :
DP(마스크, i) =DP(마스크, i-1)
우리 솔루션의 작동을 설명하는 프로그램,
예시
#include <iostream>
using namespace std;
const int N = 1000;
void SumOverSubsets(int a[], int n) {
int sum[1 << n] = {0};
int DP[N][N];
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
if (j == 0)
DP[i][j] = a[i] + a[i ^ (1 << j)];
else
DP[i][j] = DP[i][j - 1] + DP[i ^ (1 << j)][j - 1];
} else {
if (j == 0)
DP[i][j] = a[i];
else
DP[i][j] = DP[i][j - 1];
}
}
sum[i] = DP[i][n - 1];
}
for (int i = 0; i < (1 << n); i++)
cout<<sum[i]<<"\t";
}
int main() {
int A[] = {5, 7, 1, 9};
int n = 2;
cout<<"The sum over subsets is \t";
SumOverSubsets(A, n);
return 0;
} 출력
The sum over subsets is 5 12 6 22