Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước 2 n . Nhiệm vụ của chúng tôi là tạo một chương trình để tìm tổng trên tập hợp con bằng cách sử dụng lập trình động để giải quyết nó.
Chúng ta cần tính hàm, F (x) =Σ A i sao cho x &i ==i với mọi x. tức là tôi là một tập con bitwise của x.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào: A [] ={5, 7, 1, 9}, n =2
Đầu ra: 5 12 6 22
Giải thích: Với n =2, có 4 giá trị của x. Chúng là 0, 1, 2, 3.
Bây giờ, tính toán các giá trị của hàm:
F (0) =A 0 =5
F (1) =A 0 + A 1 =5 + 7 =12
F (2) =A 0 + A 2 =5 + 1 =6
F (3) =A 0 + A 1 + A 2 + A 3 =5 + 7 + 1 + 9 =22
Giải pháp cho vấn đề này bằng cách sử dụng lập trình động, chúng ta sẽ xem xét mặt nạ và tìm một tập hợp con của mỗi mặt nạ. Chúng tôi sẽ lưu trữ tập hợp con bitwise bằng cách sử dụng lập trình động, điều này sẽ giảm số lần lặp lại. Một chỉ mục có một bit đã đặt hoặc một bit chưa được đặt sẽ được truy cập bởi 2
n
mặt nạ nhiều hơn một lần.
Chúng tôi sẽ lặp lại dựa trên bit at i index:
Khi bit thứ i được đặt:
DP (mask, i) =DP (mask, i-1) U DP (mask 2 i , i-1)
Khi bit thứ i không được đặt:
DP (mask, i) =DP (mask, i-1)
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The sum over subsets is 5 12 6 22