इस समस्या में, हमें आकार 2n का एक ऐरे arr[] दिया गया है। हमारा कार्य डायनामिक प्रोग्रामिंग का उपयोग करके सबसेट्स पर योग खोजने के लिए एक प्रोग्राम बनाना है।
हमें फंक्शन की गणना करने की आवश्यकता है, F(x) = Σ Ai जैसे कि x&i == i सभी x के लिए। यानी 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
इस समस्या का समाधान डायनामिक प्रोग्रामिंग, का उपयोग करके, हम मास्क को देखेंगे और हर मास्क का बिटवाइज़ सबसेट खोजेंगे। हम डायनामिक प्रोग्रामिंग का उपयोग करके बिटवाइज़ सबसेट को स्टोर करेंगे, जो पुनरावृत्तियों की संख्या को कम करेगा। एक इंडेक्स जिसमें सेट बिट या अनसेट बिट है, 2n मास्क द्वारा एक से अधिक बार देखा जाएगा।
हम i इंडेक्स पर बिट के आधार पर पुनरावृत्ति करेंगे:
जब i-वां बिट सेट हो :
DP(mask, i) = DP(mask, i-1) U DP(mask 2i, i-1)
जब i-वां बिट अनसेट हो :
DP(mask, i) = DP(mask, 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
