Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm N số. Nhiệm vụ của chúng tôi là tạo một chương trình sẽ tìm tổng các tích của tất cả các tập hợp con có thể có.
Ở đây, chúng ta sẽ tìm tất cả các tập con và sau đó tìm tích của tất cả các phần tử cho mỗi tập con. Sau đó, cộng tất cả các giá trị để tính tổng.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {4, 5, 6} Đầu ra
209
Giải thích -
All subsets of arr[] are: {4}, {5}, {6}, {4, 5}, {5, 6}, {4, 6}, {4, 5, 6}
Sum of product
= (4) + (5) + (6) + (4*5) + (5*6) + (4*6) + (4*5*6)
= (4) + (5) + (6) + (20) + (30) + (24) + (120)
= 209 Một cách tiếp cận đơn giản để giải quyết vấn đề là tìm tất cả các tập con của tập hợp và tính tích các phần tử của mỗi tập hợp. Và thêm tất cả các sản phẩm, trả về tất cả tổng cuối cùng sau khi tất cả các tập hợp con được duyệt qua.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#include<iostream>
#include<math.h>
using namespace std;
int findSumProductSubset(int *arr, int set_length) {
unsigned int size = pow(2, set_length);
int sum = 0;
int product;
for(int counter = 1; counter < size; counter++) {
product = 1;
for(int j = 0; j < size; j++) {
if(counter & (1<<j))
product *= arr[j];
}
sum += product;
}
return sum;
}
int main() {
int arr[] = {4, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The sum of the product of all subsets is "<<findSumProductSubset(arr, n);
} Đầu ra
The sum of the product of all subsets is 209
Cách tiếp cận trên tạo ra tất cả các tập con do đó có độ phức tạp về thời gian theo cấp số nhân. Do đó, đây không phải là cách tiếp cận hiệu quả nhất.
Một cách tiếp cận hiệu quả hơn sẽ là tìm ra một khuôn mẫu cho giải pháp.
Bây giờ, hãy xem bộ ba số x, y, z.
tổng =x + y + z + xy + yz + xz + xyz
tổng =x + xz + y + yz + xy + xyz + z + 1 - 1
sum =x (1 + z) + y (1 + z) + xy (1 + z) + 1 (z + 1) - 1
sum =(x + y + xy + 1) (1 + z) - 1
sum =(x (1 + y) + 1 (1 + y)) (1 + z) - 1
sum =(1 + x) * (1 + y) * (1 + z) - 1
Điều này có thể được hình thành theo cách sau,
Đối với tập hợp n phần tử,
sum =(1+ e1) * (1 + e2) *… * (1 + en) - 1
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#include <iostream>
using namespace std;
int productOfSubsetSums(int arr[], int n) {
int sum = 1;
for (int i = 0; i < n; ++i )
sum *= (arr[i] + 1);
sum --;
return sum;
}
int main() {
int arr[] = {5, 6, 8 , 9};
int n = sizeof(arr)/sizeof arr[0];
cout<<"Sum of product of all possible subsets is "<<productOfSubsetSums(arr, n);
return 0;
} Đầu ra
Sum of product of all possible subsets is 3779