এই সমস্যায়, আমাদেরকে N সংখ্যার একটি অ্যারে [] দেওয়া হয়েছে। আমাদের কাজ হল এমন একটি প্রোগ্রাম তৈরি করা যা সমস্ত সম্ভাব্য উপসেটের পণ্যগুলির যোগফল খুঁজে পাবে৷
৷এখানে, আমরা সমস্ত উপসেট খুঁজে পাব এবং তারপর প্রতিটি উপসেটের জন্য সমস্ত উপাদানের গুণফল খুঁজে বের করব। তারপর যোগফল গণনা করতে সমস্ত মান যোগ করুন।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {4, 5, 6} আউটপুট
209
ব্যাখ্যা -
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 সমস্যা সমাধানের একটি সহজ পদ্ধতি হল সেটের সমস্ত উপসেট খুঁজে বের করা এবং প্রতিটি সেটের উপাদানের গুণফল ক্যালকুলেটর করা। এবং সমস্ত পণ্য যোগ করুন, সমস্ত উপসেটগুলি অতিক্রম করার পরে সমস্ত চূড়ান্ত যোগফল ফেরত দিন৷
৷উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#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);
} আউটপুট
The sum of the product of all subsets is 209
উপরের পদ্ধতিটি সমস্ত উপসেট তৈরি করে তাই সূচকীয় সময় জটিলতা রয়েছে। তাই, এটি সবচেয়ে কার্যকর পদ্ধতি নয়।
সমাধানের জন্য একটি প্যাটার্ন খুঁজে পেতে আরও দক্ষ পদ্ধতি হবে।
এখন, আসুন x, y, z এই তিনটি সংখ্যার একটি সেট দেখি।
যোগফল =x + y + z + xy + yz + xz + xyz
যোগফল =x + xz + y + yz + xy + xyz + z + 1 - 1
যোগফল =x(1+z) + y(1+z) + xy(1+z) + 1(z+1) - 1
যোগফল =( x + y + xy + 1 )( 1 + z ) - 1
যোগফল =( x(1 + y) + 1(1+y) )(1+z) - 1
সমষ্টি =(1 + x) * (1 + y) * (1 + z) - 1
এটি নিম্নলিখিত উপায়ে সাধারণীকরণ করা যেতে পারে,
n উপাদান সেটের জন্য,
সমষ্টি =(1+ e1) * (1 + e2) * … * (1 + en) - 1
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#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;
} আউটপুট
Sum of product of all possible subsets is 3779
