ผลรวมของผลิตภัณฑ์ของชุดย่อยที่เป็นไปได้ทั้งหมดใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของตัวเลข 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